#include <stdio.h> #include "string.h" #define error 999999 #define N 2000 int map[N][N],low[N]; void dijkstra(int start,int end,int n) { int vis[N],now=start; memset(vis,0,sizeof(vis)); memset(low,0,sizeof(low)); for(int i=0;i<=n;i++) { low[i]=map[start][i]; } vis[start]=1; while(1) { int min=error,pos; for(int i=0;i<=n;i++) if(!vis[i]&&low[i]<min){ min=low[i]; pos=i; } if(min==error) return; vis[pos]=1; for(int i=0;i<=n;i++) if(!vis[i]&&map[pos][i]+low[pos]<low[i]) low[i]=map[pos][i]+low[pos]; } } int main() { int n,m,t; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { int start,end; scanf("%d%d",&start,&end); for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { map[i][j]=error; map[j][i]=error; } for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); map[a][b]=c; map[b][a]=c; } dijkstra(start,end,n); if(10*low[end]<=100) printf("%d\n",low[end]*10); else printf("I am sorry,jlh!\n"); } } |
Double click to view unformatted code.