题意： 给定一个有向图，有路径（边）权值和节点的权值，求一个字典序最小的最短路径（中间节点权值+路径权值）
分析：此题目需要对floyd算法有比较深的了解，首先floyd是一个不断拓展路径的过程，同时也是不断增加中间节点的过程，所以累加中间节点权值的部分很好处理。
理解了floyd 算法的过程之后，记录路径也非难事，关键是题目要求的是字典序最小的最短路径。
记录路径有俩种方式：
1）
path[i][j] 记录 起点为i ，终点为j 的路径上j 的直接前驱
View Code void init(int n){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&g[i][j]); if(i!=j && g[i][j]!=-1) path[i][j]=i; else path[i][j]=-1; } for(int i=1;i<=n;i++) scanf("%d",&b[i]);}void floyd(int n){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) { if(i==k || g[i][k]==-1) continue; for(int j=1;j<=n;j++) { if(i==j || j==k) continue; if(g[k][j]==-1) continue; int newdis=g[i][k]+g[k][j]+b[k];//k为中间节点 if(g[i][j]==-1 || g[i][j]>newdis) { g[i][j]=newdis; path[i][j]=path[k][j]; } else if(g[i][j]==newdis && path[i][j]>path[k][j]) path[i][j]=path[k][j]; } }} 事实上，上面这种方法并不能保证字典序，但不能否定的是，这是一种记录路径的方法
为什么不能保证字典序呢？看一下更新路径的代码：if(g[i][j]==newdis && path[i][j]>path[k][j])
path[i][j]=path[k][j];更新的是j的直接前驱，其实也很明显了，单纯比较j 的直接并不能保证字典序的大小。。因为i的直接后继才是关键
2）
path[i][j] 记录起点为i ，中终点为j 的路径上i 的直接后继
View Code inline void init(int n){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&g[i][j]); path[i][j]=j; } for(int i=1;i<=n;i++) scanf("%d",&b[i]);}inline void floyd(int n){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) { if(i==k || g[i][k]==-1) continue; for(int j=1;j<=n;j++) { if(i==j || j==k) continue; if(g[k][j]==-1) continue; int newdis=g[i][k]+g[k][j]+b[k]; if(g[i][j]==-1 || g[i][j]>newdis) { g[i][j]=newdis; path[i][j]=path[i][k]; } else if(g[i][j]==newdis && path[i][j]>path[i][k]) path[i][j]=path[i][k]; } }} 这种方法就保证了字典序，因为每次拓展路径的时候都是保证起点的直接后继字典序，这样的路径拼接的时候才能保证字典序最小
看完整的代码吧，还有要注意的一点是，数据中有可能出现起点等于终点的情况
View Code #include#include #include using namespace std;const int N = 50+10;int path[N][N],g[N][N];int b[N];inline void init(int n){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&g[i][j]); path[i][j]=j; } for(int i=1;i<=n;i++) scanf("%d",&b[i]);}inline void floyd(int n){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) { if(i==k || g[i][k]==-1) continue; for(int j=1;j<=n;j++) { if(i==j || j==k) continue; if(g[k][j]==-1) continue; int newdis=g[i][k]+g[k][j]+b[k]; if(g[i][j]==-1 || g[i][j]>newdis) { g[i][j]=newdis; path[i][j]=path[i][k]; } else if(g[i][j]==newdis && path[i][j]>path[i][k]) path[i][j]=path[i][k]; } }}inline void printpath(int s,int t){ printf("Path: %d",s); while(path[s][t]!=t) { printf("-->%d",path[s][t]); s=path[s][t]; } printf("-->%d\n",t);}int main(){ int n,s,t; while(scanf("%d",&n)==1 && n) { init(n); floyd(n); while(scanf("%d %d",&s,&t)==2) { if(s==-1 && t==-1) break; printf("From %d to %d :\n",s,t); if(s==t) { printf("Path: %d\n",s); printf("Total cost : 0\n\n"); continue; } printpath(s,t); printf("Total cost : %d\n\n",g[s][t]); } } return 0;}