#include<stdio.h># define max 0xfffffffint n,m,map[201][201];int min(int x,int y){ return x>y?y:x;}void getmap()//初始化路径。{ int i,j,a,b,l; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i==j) map[i][j]=0; else map[i][j]=max; } } for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&l); map[a][b]=map[b][a]=min(map[a][b],l); }}void floyd(int s,int e){ int i,j,k; for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) map[i][j]=min(map[i][j],map[i][k]+map[k][j]); if(map[s][e]>=max) printf("-1/n"); else printf("%d/n",map[s][e]);}int main(){ int s,e; while(~scanf("%d%d",&n,&m)) { getmap(); scanf("%d%d",&s,&e); floyd(s,e); } return 0;}
新闻热点
疑难解答