POJ 1125最短路的水题

#include<cstdio> #define MAX 0x3f3f3f3f using namespace std; int main() { int m; //printf("几组数据\n"); //scanf("%d",&n); while(scanf("%d",&m)!=EOF&&m!=0) { int min3=MAX; int ans; //int m; //printf("有几个节点\n"); //scanf("%d",&m); //for(int r=1; r<=m; r++) //{ int map[m+5][m+5]; for(int i=1; i<=m; i++) { for(int u=1; u<=m; u++) { map[i][u]=MAX; } } for(int i=1; i<=m; i++) { int e,in,len; //printf("第%d个节点与几个节点相连？\n",i); scanf("%d",&e); //printf("与谁相连，距离为多少\n"); for(int u=1; u<=e; u++) { scanf("%d %d",&in,&len); map[i][in]=len; } } for(int r=1; r<=m; r++) { int vis[m+5]; for(int i=1; i<=m; i++) { vis[i]=0; } int dis[m+5]; int ben,end; //printf("输入起点和终点\n"); //scanf("%d %d",&ben,&end); for(int i=1; i<=m; i++) { dis[i]=map[r][i]; } vis[r]=1; dis[r]=0; int p; for(int i=1; i<=m-1; i++) { int min=MAX; for(int j=1; j<=m; j++) { if(!vis[j]&&min>dis[j]) { min=dis[j]; p=j; } } vis[p]=1; for(int j=1; j<=m; j++) { if(!vis[j]&&min+map[p][j]<dis[j]) { dis[j]=min+map[p][j]; } } } int max,ant; max=0; for(int j=1; j<=m; j++) { if(max<dis[j]) { max=dis[j]; ant=r; } } if(max<min3) { min3=max; ans=ant; } } printf("%d %d\n",ans,min3); } return 0; }