#include "stdio.h" #include "string.h" #define error 999999999 int start,end,pre[10005],dis[10005],cnt,m,n,t; struct node{ int to,next,v; }T[20005]; void add(int a,int b,int c) { T[cnt].to=b; T[cnt].v=c; T[cnt].next=pre[a]; pre[a]=cnt++; } void spfa() { int vis[10005]; int front=0,last=0,pos; memset(vis,0,sizeof(vis)); for(int i=0;i<=m;i++) dis[i]=error; dis[start]=0; vis[start]=1; pos=start; for(int i=pre[pos];i!=-1;i=T[i].next) { int y=T[i].to; dis[y]=T[i].v; } while(1) { int min=error; if(pos==end) return; for(int i=0;i<=m;i++) if(!vis[i]&&dis[i]<min) { min=dis[i]; pos=i; } vis[pos]=1; if(min==error) return; for(int i=pre[pos];i!=-1;i=T[i].next) { int y=T[i].to; if(!vis[y]) dis[y]=(dis[pos]+T[i].v)<dis[y]?(dis[pos]+T[i].v):dis[y]; } } } int main() { while(scanf("%d%d%d",&m,&n,&t)!=EOF) { cnt=0; memset(pre,-1,sizeof(pre)); scanf("%d%d",&start,&end); for(int i=0;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } spfa(); if(10*dis[end]<=t) printf("%d\n",dis[end]*10); else printf("I am sorry,jlh!\n"); } } |
Double click to view unformatted code.