记录编号	130408	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-10-22 08:14:52	内存使用	8.11 MiB

#include<cstdio>
#include<cstring> 
#include<queue>
#define  sizeque  2000000
struct aaa{
	int to;
	int next;
	int data;
}a[12901];
int dis[5001];
bool b[5001];
int head0[5001];
int t=0,c=0,ts=0,te=0;
int tot=0;
int q[2000001],head=1,tail=0;

void init();
void work();
void outit();
void insert(int ,int ,int );

inline int front() { return q[(head)%sizeque] ; } 
inline void push(int x) { q[(++tail)%sizeque] = x ; } 
inline void pop() { head ++ ;}
inline bool empty() { return head > tail ; }

int main()
{
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	init();
	work();
	outit();
	return 0; 
}
void init()
{
	scanf("%d%d%d%d",&t,&c,&ts,&te);
	//printf("\n%d %d\n",ts,te);
	for(int i=1;i<=c;i++)
	{
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		insert(x,y,v);
		
	}
	//printf("\n%d %d\n",ts,te);
}
void work()
{
	//std::queue <int > q;
	memset(dis,0x7f,sizeof(dis));
	memset(b,0,sizeof(b));
	push(ts);
	dis[ts]=0;
	b[ts]=1;
	while(!empty())
	{
		int x=front();
		for(int i=head0[x];i!=0;i=a[i].next)
		{
			int tt=a[i].to;
			if(dis[tt]>dis[x]+a[i].data)
			{
				dis[tt]=dis[x]+a[i].data;
				if(!b[tt])
				{
					push(tt);
					b[tt]=1;
				}
			}
		}
		pop();
		b[x]=0;
	}
}
void outit()
{
	printf("%d\n",dis[te]);
}
void insert(int x,int y,int v)
{
	tot++;
	a[tot].to=y;
	a[tot].next=head0[x];
	a[tot].data=v;
	head0[x]=tot;
	tot++;
	a[tot].to=x;
	a[tot].next=head0[y];
	a[tot].data=v;
	head0[y]=tot;
}