http://acm.hdu.edu.cn/showproblem.php?pid=1385
在未学习Dijkstra记录路径之前，对于这道题目，复杂度不大的前提下，我选择了用Floyd记录路径。
pre数组记录路径，map为原图，两点之间无路时为INF.
int pre[vex_num][vex_num],map[vex_num][vex_num]; void Floyd() { int i,j,k; for(i=0;i<vex_num;i++) { for(j=0;j<vex_num;j++) { if(map[i][j]!=INF) pre[i][j]=j;//i的后继元素是j else pre[i][j]=-1; } } for(k=0;k<vex_num;k++) { for(i=0;i<vex_num;i++) { for(j=0;j<vex_num;j++) { if(map[i][k]+map[k][j]<map[i][j]) { map[i][j]=map[i][k]+map[k][j]; pre[i][j]=pre[i][k]; } else if(map[i][k]+map[k][j]==map[i][j]) { if(pre[i][j]>pre[i][k]) pre[i][j]=pre[i][k];//pre数组中记录的是最小的 } } } } }
HDU 1385这道题目意思很简单，输入一张图，求start到end两点之间的最短距离并且输出路径，当存在多条路径时，输出lexically最小的那条路径。这道题目还有一个地方是:每个地方都有一个权值，这个权值无需加到原图上。
思路：构图+Floyd( 记录路径的)
贴下代码：
#include<stdio.h> #include<string.h> #define MAXN 100 #define INF 10000000 int map[MAXN][MAXN],path[MAXN][MAXN]; int output[MAXN],B[MAXN]; void Floyd(int n) { int i,j,k; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ path[i][j]=j; } } for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(map[i][k]+map[k][j] + B[k]<map[i][j]){ map[i][j]=map[i][k]+map[k][j] + B[k]; path[i][j]=path[i][k]; } else if(map[i][k]+map[k][j] + B[k]==map[i][j]){ if(path[i][j]>path[i][k]) path[i][j]=path[i][k]; } } } } } int main() { int n,i,j,a; while(scanf("%d",&n)!=EOF&&n){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&a); if(a==-1) map[i][j]=INF; else map[i][j]=a; } }//构图 for(i=1;i<=n;i++) scanf("%d",&B[i]); Floyd(n); int s,e; while(scanf("%d%d",&s,&e)!=EOF){ if(s==-1&&e==-1) break; printf("From %d to %d :/n",s,e); printf("Path: %d",s); int tt=s; while(tt!=e){ printf("-->%d",path[tt][e]); tt=path[tt][e]; } printf("/nTotal cost : %d/n/n",map[s][e]); } } return 0; }
