Hint
其实就是求最长路加了一个限制条件
开始用的是disktra改了改模版发现不对，数组开不开也就改不动了
#include <stdio.h>#define maxnum 1000#define maxint 999999int dist[maxnum]; //表示当前点到源点的最短路径长度int prev[maxnum]; //记录当前点的前一个结点int c[maxnum][maxnum]; //记录图的两点间路径长度int n,line;//图的结点数和路径数void Dij(int n,int v,int *dist, int *prev, int c[maxnum][maxnum]) //v代表源点吗？{int s[maxnum] = {0};//判断是否已将该点存入到s数组中int i;for(i = n;i>=1;i–){dist[i] = c[v][i];//将从源点到i点的初始距离存入数组dist中s[i] = 0;//初始化为全部没有用过该点if(dist[i] == 0)//如果源点到该点的距离为无穷大，则该点前面没有连接点prev[i] = 0;elseprev[i] = v;}dist[v] = 0; //源点到源点的距离初始化为0s[v] = 1;//把源点存入数组s//依次将未放入集合s中的节点，取dist【】最小值的节点放进去//一旦s包含了所有v中顶点，dist就记录了从源点到所有其他顶点之间的最短路径//注意是从第二个节点开始，第一个结点表示源点 for(i = 2;i<=n;i++) {int tmp = 0;int u = v;for(int j = n;j>=1;j–) //找出当前未使用的点j的dist【j】最小值{if((!s[j]) && dist[j] > tmp){u = j;//u储存当前邻接点中距离最小的点的号码tmp = dist[j];}}s[u] = 1;//一次for循环结束后，便找出了所有未使用的点中距离最小的点，，将此点存入集合s中//更新dist值for(int j = n;j>=1;j–){if((!s[j]) && c[u][j]>0) //确定该点没有加入s集合，并且存在这段距离，即经过该点{int newdist = dist[u] + c[u][j];//判断经过该点到j的距离和不经过该点到j的距离的大小if(newdist > dist[j]){dist[j] = newdist;prev[j] = u;}}} }}//查找从源点v到终点u的路径，并输出void searc(int *prev,int v,int u){int que[maxnum];//该数组保存路径int tot = 1;que[tot] = u;//从终点开始找，一直找到源点v并记录路径tot++;int tmp = prev[u];while(tmp != v){que[tot] = tmp;tot++;tmp = prev[tmp];}que[tot] = v;for(int i = tot;i>=1;i–)//输出{if(i!=1)printf("%d->",que[i]);elseprintf("%d\n",que[i]);}//注意，若题目要求输出距离，则直接输出dist【u】即可}int main(){scanf("%d %d",&n,&line);int p,q,len;for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++)c[i][j] = 0;}for(int i = 1;i<=line;i++){dist[i] = 0;}for(int i = 1;i<=line;i++){scanf("%d%d%d",&p,&q,&len);if(len>c[p][q]){c[p][q] = len;//c[q][p] = len;}}Dij(n,1,dist,prev,c);printf("从源点到终点的最短路径长度为%d\n",dist[n]);searc(prev,1,n);return 0;}下面是spfa的方法
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<queue>#define INF 0x3f3f3f3fusing namespace std;struct node{int u,v,w,next;} edge[500010];int cnt,n,m,head[10010],dis[10010],vis[10010],pre[10010], pre1[10005];int id[10005],cd[10005];void add(int u,int v,int len){edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=len;edge[cnt].next=head[u];head[u]=cnt++;}void spfa(int u,int v,int n){memset(vis,0,sizeof(vis));memset(pre,INF,sizeof(pre));memset(dis,-INF,sizeof(dis));queue<int>q;q.push(u);dis[u]=0;vis[u]=1;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int p=head[x]; p!=-1; p=edge[p].next){if(dis[edge[p].v]<dis[x]+edge[p].w||(dis[edge[p].v]==dis[x]+edge[p].w&&x<pre[edge[p].v])){dis[edge[p].v]=dis[x]+edge[p].w;pre[edge[p].v]=x;if(!vis[edge[p].v]){vis[edge[p].v]=1;q.push(edge[p].v);}}}}int k=0;printf("%d\n",dis[v]);for(int i=v; i!=INF; i=pre[i])pre1[k++]=i;for(int i=1; i<k; i++)printf("%d %d\n",pre1[i-1],pre1[i]);}int main(){while(~scanf("%d %d",&n,&m)){int u,v,w;memset(head,-1,sizeof(head));memset(id,0,sizeof(id));memset(cd,0,sizeof(cd));while(m–){scanf("%d %d %d",&u,&v,&w);add(v,u,w);id[u]++;cd[v]++;}for(int i=1; i<=n; i++){if(id[i]==0)u=i;if(cd[i]==0)v=i;}spfa(u,v,n);}return 0;}
接受自己的失败面，是一种成熟，更是一种睿智;
