#include <stdio.h> #include "string.h" #define error 999999; int n,m,t,pre,end,vis[10001],low[10001]; struct node{ int ans[10001],end[10001],sum; }p[10001]; void add(struct node *ss,int a,int b,int c) { ss[a].end[ss[a].sum]=b; ss[a].ans[ss[a].sum]=c; ss[a].sum++; } void fun() { for(int i=0;i<=n;i++) low[i]=error; for(int i=0;i<p[pre].sum;i++) low[p[pre].end[i]]=p[pre].ans[i]; vis[pre]=1; while(1) { int min=error; int pos; for(int i=0;i<=n;i++) { if(vis[i]!=1&&low[i]<min) { min=low[i]; pos=i; } } if(min==999999) break; vis[pos]=1; for(int i=0;i<p[pos].sum;i++) { if(!vis[p[pos].end[i]]) low[p[pos].end[i]]=low[pos]+p[pos].ans[i]<low[p[pos].end[i]]?low[pos]+p[pos].ans[i]:low[p[pos].end[i]]; } } } int main() { while(scanf("%d%d%d",&n,&m,&t)!=EOF) { scanf("%d%d",&pre,&end); memset(vis,0,sizeof(vis)); memset(low, 0, sizeof(low)); for(int i=0;i<=n;i++) p[i].sum=0; for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(p,a,b,c); add(p,b,a,c); } fun(); if(10*low[end]<=100) printf("%d\n",low[end]*10); else printf("I am sorry,jlh!\n"); } } |
Double click to view unformatted code.