记录编号	458350	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-10-11 07:58:14	内存使用	0.38 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
const int maxn=2510;
int n,m,st,en;
vector<int>g[maxn],w[maxn];
int d[maxn];
bool done[maxn];
struct dd{
	int v,id;
	inline bool operator < (const dd & a)const {
		return v>a.v;
	}
};
inline void dij(){
	memset(d,127,sizeof(d));
	d[st]=0;
	priority_queue<dd>q;
	q.push((dd){0,st});
	while(!q.empty()){
		dd tou=q.top();q.pop();
		int u=tou.id;
		if(done[u])continue;
		done[u]=true;
		for(int i=0;i<(int)g[u].size();i++){
			int v=g[u][i];
			if(d[v]>d[u]+w[u][i]){
				d[v]=d[u]+w[u][i];
				q.push((dd){d[v],v});
			}
		}
	}
}
int main(){
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	n=read();m=read();st=read();en=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),ww=read();
		g[u].push_back(v);
		g[v].push_back(u);
		w[u].push_back(ww);
		w[v].push_back(ww);  
	}
	dij();
	printf("%d\n",d[en]);
	return 0;
}