简单最短路
#include<stdio.h> #include<string.h> #define inf 0x3fffffff int n,m,k,map[60][60]; int st,ed; int main() { int i,j,x,y,t,op=1,p,w; char s[50][3],ch1[3],ch2[3]; scanf("%d",&t); printf("SHIPPING ROUTES OUTPUT\n\n"); while(t--) { scanf("%d%d%d",&n,&m,&k); for(i=1;i<=n;i++) { map[i][i]=0; for(j=i+1;j<=n;j++) map[i][j]=map[j][i]=inf; } for(i=1;i<=n;i++) scanf("%s",s[i]); for(i=0;i<m;i++) { scanf("%s%s",ch1,ch2); for(j=1;j<=n;j++) { if(strcmp(ch1,s[j])==0) x=j; if(strcmp(ch2,s[j])==0) y=j; } map[x][y]=map[y][x]=1; } for(p=1;p<=n;p++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]>map[i][p]+map[p][j]) map[i][j]=map[i][p]+map[p][j]; printf("DATA SET %d\n\n",op++); while(k--) { scanf("%d%s%s",&w,ch1,ch2); for(i=1;i<=n;i++) { if(strcmp(ch1,s[i])==0) x=i; if(strcmp(ch2,s[i])==0) y=i; } if(map[x][y]<inf) printf("$%d\n",map[x][y]*w*100); else printf("NO SHIPMENT POSSIBLE\n"); } printf("\n"); } printf("END OF OUTPUT\n"); return 0; }