hdu 1385 Minimum Transport Cost (最小字典序最短路径)

题目链接: hdu 1385

题目大意: 给出N个点的邻接矩阵，求任意两点的最短路径

若有多条路径，输出字典序最小的路径

解题思路: 边为-1的时候，换成INF，用Floyd求出最短路径，path[ i ][ j ]表示路径i到j经过的点

dis[ i ][ j ]=Min( dis[ i ][ j ]，dis[ i ][ k ] + dis[ k ][ j ] )，更新了dis[ i ][ j ]之后，记录path[ i ][ j ]=path[ i ][ k ]

代码:

#include 
  
   
#include 
   
     #include 
    
      #define MAX 205 #define INF 0x3f3f3f3f int dis[MAX][MAX],path[MAX][MAX]; int main() { int i,j,n,m,k,t,V[MAX],a,b; while(scanf("%d",&n)!=EOF&&n) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { path[i][j]=j; scanf("%d",&dis[i][j]); if(dis[i][j]==-1) dis[i][j]=INF; } } for(i=1;i<=n;i++) scanf("%d",&V[i]); for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { t=dis[i][k]+dis[k][j]+V[k]; if(t
     
      %d",path[m][b]); m=path[m][b]; } printf("\nTotal cost : %d\n",dis[a][b]); puts(""); } } return 0; }