记录编号	220408	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-01-18 15:32:47	内存使用	0.53 MiB

#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstdio>
#include<ctime>
#include<cstdio>
#include<cstring>
const int maxn=2510;
int m,n,qi,zhong,len=0,head[maxn];
const int maxe=17500;
using namespace std;
	struct Edge
{
	int dis,to,next;
}e[maxe];
void Spfa(int);
void Init();
void Insert(int,int,int);
int main()
{
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	Init();
	Spfa(qi);
	//while(1);
	return 0;
}
void Init()
{   
	memset(head,-1,sizeof(head));
	memset(e,0,sizeof(e));
    cin>>n>>m>>qi>>zhong;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		Insert(x,y,z);
		Insert(y,x,z);
	}
	
}
	void Insert(int x,int y,int z)
{
	len++;
	e[len].to=y;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
void Spfa(int x)
{
	int d[maxn];
	memset(d,0x7f,sizeof(d));
	bool f[maxn]={0};
	queue<int> q;
	d[x]=0;
	q.push(x);
	f[x]=1;	
	while(!q.empty())
	{	
		int k=q.front();q.pop();f[k]=0;
		for(int i=head[k];i!=-1;i=e[i].next)
  		{
	 		int j=e[i].to;	 
			if(d[j]>d[k]+e[i].dis)
   			{
				d[j]=d[k]+e[i].dis;
				if(!f[j])
				{
					q.push(j);
					f[j]=1;
				}
   			}
   		}  
}

		cout<<d[zhong];
}