View Code of Problem 2596

#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.


Back to problem 2596