记录编号	314469	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-10-03 15:09:51	内存使用	0.58 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN=2510;
const int MAXM=20000;
int dis[MAXN];
struct heap{
	struct NODE{
		int l,r,ch;
	}node[MAXN];
	int sta[MAXN],topt,root;
	heap(){root=0;}
	void push(int p){
		if(!root)root=p;
		else root=join(root,p);
	}
	int join(int a,int b){
		if(dis[a]<dis[b])
			std::swap(a,b);
		node[a].l=b;
		node[a].r=node[b].ch;
		node[node[b].ch].l=a;
		node[b].ch=a;
		return b;
	}
	void update(int p){
		if(p!=root){
			if(node[node[p].l].ch==p)
				node[node[p].l].ch=node[p].r;
			else 
				node[node[p].l].r =node[p].r;
			if(node[p].r!=0)
				node[node[p].r].l=node[p].l;
			node[p].l=node[p].r=0;
			root=join(root,p);
		}
	}
	void pop(){
		if(!node[root].ch)root=0;
		else {
			topt=0;
			int p=node[root].ch;
			while(p){
				if(node[p].r){
					int v=node[p].r;
					int k=node[v].r;
					node[p].l=node[p].r=0;
					node[v].l=node[v].r=0;
					sta[++topt]=join(p,v);
					p=k;
				}else {
					sta[++topt]=p;
					node[p].l=node[p].r=0;
					break;
				}
			}root=sta[topt];
			for(int i=1;i<topt;++i)
				root=join(root,sta[i]);
		}
	}
}q;
struct PATH{
	int to,next,dis;
	PATH(){to=next=-1;}
};
struct PIC{
	int head[MAXN];
	bool vis[MAXN];
	PATH table[MAXM];
	PIC(){memset(head,-1,sizeof(head));}
	void add(int from,int to,int dis){
		static int lens=0;
		table[++lens].next=head[from];
		table[lens].to=to;
		table[lens].dis=dis;
		head[from]=lens;
	}
	int DIJSTRA(int FROM,int TO,int N){
		memset(dis,63,sizeof(dis));
		dis[FROM]=0;q.push(FROM);vis[FROM]=true;
		while(q.root){
			int p=q.root;q.pop();vis[p]=false;
		//	printf("p::%d\n",p);
			if(p==TO)return dis[p];
			for(int i=head[p];i!=-1;i=table[i].next){
				if(dis[table[i].to]>dis[p]+table[i].dis){
					dis[table[i].to]=dis[p]+table[i].dis;
					if(vis[table[i].to])q.update(table[i].to);
					else q.push(table[i].to),vis[table[i].to]=true;
				}
			}
		}return dis[TO];
	}
}pic;
int main(){
	freopen("heatwvx.in","r",stdin);
	freopen("heatwvx.out","w",stdout);
	int N,M,FROM,TO,a,b,c,d;
	scanf("%d%d%d%d",&N,&M,&FROM,&TO);
	for(int i=1;i<=M;++i){
		scanf("%d%d%d",&a,&b,&c);
		pic.add(a,b,c);
		pic.add(b,a,c);
	}printf("%d",pic.DIJSTRA(FROM,TO,N));
	return 0;
}