hdu 1385（zoj 1456）Minimum Transport Cost(最短路，输出路径，Floyd实现)

图论的最短路问题，这道题多了个每个点的权值（就是tax值，相当于过路费），还有要求输出最短路径，如果路长相等，以字典序为准。

我用的是Floyd（因为……dijkstra我还不会路径回溯……）。另设一个和map[][]等大的数组path[][]用来保存路径，首先把path[i][j]初始化为j，也就是说path[i][j]用来保存 i --> j 的最短路径中 i 的最优后驱（即最近），在Floyd三重循环时，一直更新path。

到结束时，以 i 找到 j 就可以了（这里有点递归的意思，以后好好想想）。

 

上代码：

 

#include<stdio.h>#include<string.h>#define MAX 999999999int n,map[101][101],path[101][101],tax[101];void getmap()//图的初始化，包括tax[],path[]的初始化{int i,j;for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&map[i][j]);if(map[i][j]==-1)map[i][j]=MAX;path[i][j]=j;}}for(i=1;i<=n;i++)scanf("%d",&tax[i]);}void floyd(){int i,j,k,t;for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){t=map[i][k]+map[k][j]+tax[k];if(t<map[i][j]) //路径权值{map[i][j]=t;path[i][j]=path[i][k];}else if(t==map[i][j]) //字典序{if(path[i][j]>path[i][k])path[i][j]=path[i][k];}}}}int main(){int i,j,k;while(scanf("%d",&n),n){memset(path,0,sizeof(path));memset(map,0,sizeof(map));memset(tax,0,sizeof(tax));getmap();floyd();while(scanf("%d%d",&i,&j),i!=-1){printf("From %d to %d :/n",i,j);printf("Path: %d",i);k=i;while(k!=j) //路径的输出{printf("-->%d",path[k][j]);k=path[k][j];}printf("/n");printf("Total cost : %d/n/n",map[i][j]);}}return 0;}