学步园

简单最短路，没有二叉堆优化。

/*
 * TYVJ-1031 热浪
 * mike-w
 * 2011-11-1
 * ----------------
 * 最短路
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 2555
#define INF 99999
#define FILE_INPUT

int f[SIZE][SIZE];
int d[SIZE];
int tag[SIZE];
int T,C,TS,TE;

int extract(void)
{
	int ret=-1,i;
	for(i=1;i<=T;i++)
		if(!tag[i] && d[i]<INF)
		{
			ret=i;
			break;
		}
	for(;i<=T;i++)
		if(!tag[i] && d[i]<d[ret])
			ret=i;
	return ret;
}

int calc(void)
{
	int i,node;
	for(i=0;i<=T;i++)
		d[i]=INF;
	d[TS]=0;
	while((node=extract())!=-1)
	{
		if(node==TE) break;
		tag[node]=1;
		for(i=1;i<=T;i++)
			if(!tag[i] && f[node][i]>0 && d[node]+f[node][i]<d[i])
				d[i]=d[node]+f[node][i];
	}
	return d[TE];
}

int main(void)
{
	int i,t1,t2,t3;
#ifdef FILE_INPUT
	freopen("in","r",stdin);
#endif
	scanf("%d%d%d%d",&T,&C,&TS,&TE);
	for(i=0;i<C;i++)
	{
		scanf("%d%d%d",&t1,&t2,&t3);
		if(f[t1][t2]==0) f[t1][t2]=f[t2][t1]=t3;
		else if(f[t1][t2]>t3) f[t1][t2]=f[t2][t1]=t3;
	}
	printf("%d\n",calc());
	return 0;
}