记录编号	467639	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-10-30 20:59:01	内存使用	0.59 MiB

#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
#include <functional>
using namespace std;
const int inf=1111111111;
int t,c,s,e;
typedef pair<int,int> P;
struct edge {int u,v,l;} edges[14000];
int head[14000]={0},nextt[14000]={0};
inline void add_edge(int u,int num) {
	nextt[num]=head[u];
	head[u]=num;
}
int d[3000];
inline int dijkstra() {
	priority_queue<P,vector<P>,greater<P> > pq;
	for(int i=0;i<t;++i) {
		d[i]=inf;
	}
	d[s]=0;
	pq.push(P(0,s));
	while(pq.size()) {
		P now=pq.top();pq.pop();
		if(d[now.second]<now.first) {
			continue;
		}
		for(int i=head[now.second];i!=-1;i=nextt[i]) {
			edge e=edges[i];
			if(d[e.u]+e.l<d[e.v]) {
				d[e.v]=d[e.u]+e.l;
				pq.push(P(d[e.v],e.v));
			}
		}
	}
	return d[e];
}
int main() {
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	scanf("%d%d%d%d",&t,&c,&s,&e);s--;e--;
	for(int i=0;i<2*c;++i) {
		head[i]=-1;
		nextt[i]=-1;
	}
	for(int i=0;i<c;++i) {
		scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].l);
		edges[i].u--;edges[i].v--;
		edges[c+i]=(edge){edges[i].v,edges[i].u,edges[i].l};
		add_edge(edges[i].u,i);
		add_edge(edges[i+c].u,i+c);
	}
	printf("%d\n",dijkstra());
	fclose(stdin);
	fclose(stdout);
	return 0;
}