题目链接: 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 <stdio.h> #include <stdlib.h> #include <string.h> #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<dis[i][j]) { dis[i][j]=t; path[i][j]=path[i][k]; //更新 } else if(t==dis[i][j]&&path[i][k]<path[i][j]) //最小字典序 path[i][j]=path[i][k]; } } } while(scanf("%d%d",&a,&b)) { if(a==-1&&b==-1) break; printf("From %d to %d :\nPath: %d",a,b,a); m=a; while(m!=b) { printf("-->%d",path[m][b]); m=path[m][b]; } printf("\nTotal cost : %d\n",dis[a][b]); puts(""); } } return 0; }