记录编号	221595	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-01-24 16:41:53	内存使用	0.48 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
int n;
const int maxn = 2500 + 10 ;
struct Edge{
	int to,next,dis;
}G[6200*2 + 10]; //无向图，边数 * 2  
int d[maxn],cnt,head[maxn];
void add(int u,int v,int temp){
	cnt++;
	G[cnt].to = v;
	G[cnt].dis = temp ;
	G[cnt].next = head[u];
	head[u] = cnt ;
}
struct a{
	int nub,dis;
	bool operator < (const a &rhs) const {
		return dis > rhs.dis ;
	}
	a(int b=0,int d=0): nub(b),dis(d) {}
};
void djs(int s){
	memset(d,0x7f,sizeof(d));
	priority_queue<a>Q;
	d[s] = 0;Q.push( a(s,0) );
	while( !Q.empty() ){
		a temp = Q.top();Q.pop();
		if( d[ temp.nub ] != temp.dis ) continue ;
		for(int i=head[temp.nub];i!=0;i=G[i].next)
			if( d[G[i].to] > d[temp.nub] + G[i].dis ){
				d[G[i].to] = d[temp.nub] + G[i].dis;
				Q.push( a(G[i].to,d[ G[i].to ]) );
			}
	//for(int i=1;i<n;i++) cout<<" "<<d[i];
	//cout<<endl;
	}	
}
int main(){
	freopen("heatwvx.in","r",stdin);
 	freopen("heatwvx.out","w",stdout);
	int e,s,to;scanf("%d%d%d%d",&n,&e,&s,&to);
	int u,v,temp;
	for(int i=0;i<e;i++){
		scanf("%d%d%d",&u,&v,&temp);
		add(u,v,temp);
		add(v,u,temp);
	}
	djs(s);
	printf("%d",d[to]);
	return 0;
}