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

#include<cstdio>
#include<cstring>
#define lchild(a) (a<<1)+1
#define rchild(a) (a<<1)+2
#define parent(a) (a-1)>>1
struct node{
	int to,totdis;
	node(int _to=0,int _totdis=0){
		to = _to;
		totdis = _totdis;
	}
}heap[10000];
int size;
int swap(int a,int b){
	node tmp = heap[a];
	heap[a] = heap[b];
	heap[b] = tmp;
	return b;
}
void del(){
	heap[0]=heap[--size];
	int pt = 0;
	while(rchild(pt)<size){
		int flag = 0;
		if(heap[lchild(pt)].totdis<heap[pt].totdis)flag+=1;
		if(heap[rchild(pt)].totdis<heap[pt].totdis)flag+=2;
		if(flag==0)break;
		else if(flag==1)pt = swap(pt,lchild(pt));
		else if(flag==2)pt = swap(pt,rchild(pt));
		else if(heap[lchild(pt)].totdis<heap[rchild(pt)].totdis)pt = swap(pt,lchild(pt));
		else pt = swap(pt,rchild(pt));
	}
	if(rchild(pt)==size&&heap[lchild(pt)].totdis<heap[pt].totdis)swap(pt,lchild(pt));
}
void add(node a){
	heap[size++]=a;
	int pt = size-1;
	while(pt&&heap[parent(pt)].totdis>heap[pt].totdis){
		pt = swap(pt,parent(pt));
	}
}
struct edge{
	int to,dis,next;
}lst[10000];
int len;
int head[2550];
void insert(int v1,int v2,int _dis){
	lst[len].to=v2;
	lst[len].next = head[v1];
	lst[len].dis = _dis;
	head[v1]=len++;
}
int ans[2550];
bool visited[2550];
void djs(int s){
	memset(ans,63,sizeof(ans));
	memset(visited,0,sizeof(visited));
	for(int pt = head[s];pt;pt=lst[pt].next){
		add(node(lst[pt].to,lst[pt].dis));
		ans[lst[pt].to]=lst[pt].dis;
	}
	ans[s]=0;
	while(size){
		while(size&&visited[heap[0].to])del();
		visited[heap[0].to]=true;
		int v = heap[0].to;
		int pt = head[heap[0].to];
		while(pt){
			if(ans[lst[pt].to]>ans[v]+lst[pt].dis){
				ans[lst[pt].to]=ans[v]+lst[pt].dis;
				add(node(lst[pt].to,ans[lst[pt].to]));
			}
			pt = lst[pt].next;
		}
	}
}
int main(){
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	int n,m,start,end;
	scanf("%d %d %d %d",&n,&m,&start,&end);
	int a,b,c;
	for(int i = 0;i<m;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
		insert(b,a,c);
	}
	djs(start);
	printf("%d",ans[end]);
	fclose(stdin);fclose(stdout);
	return 0;
}