记录编号	96677	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]路障	最终得分	100
用户昵称	Suke	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2014-04-14 14:59:04	内存使用	0.89 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define M 50005
#define N 255
int n,m,e,ans,edge,del,size;
int head[M],w[M],next[M];
int p[N],d[3][N],pos[N];
int heap[1010];
bool v[N];
void add(int x,int y,int c){
	head[++e]=y;w[e]=c;
	next[e]=p[x];
	p[x]=e;
}
void up(int x,int opt){
	int y;
	while(x>1){
		y=x>>1;
		if (d[opt][heap[x]]<d[opt][heap[y]]){
			swap(pos[heap[x]],pos[heap[y]]);
			swap(heap[x],heap[y]);
			x=y;
			y=x>>1;
		}
		else break;
	}
}
void down(int x,int n,int opt){
	int y=x<<1;
	while(y<=n){
		if (y<n && d[opt][heap[y]]>d[opt][heap[y+1]]) y++;
		if (d[opt][heap[x]]>d[opt][heap[y]]){
			swap(pos[heap[x]],pos[heap[y]]);
			swap(heap[x],heap[y]);
			x=y;
			y=x<<1;
		}
		else break;
	}
}
void heap_dj(int opt){
	memset(d[opt],0x3f3f3f3f,sizeof(d[opt]));
	memset(v,0,sizeof(v));
	memset(pos,0,sizeof(pos));
	int st;
	if (opt==1) st=n;
	else st=1;
	d[opt][st]=0;
	heap[size=1]=st;
	v[st]=true;
	pos[st]=1;
	int x,j,y;
	while(size){
		x=heap[1];
		for(j=p[x];j;j=next[j])
		if(d[opt][y=head[j]]>d[opt][x]+w[j])
		{
		   d[opt][y]=d[opt][x]+w[j];
		   up(pos[y],opt);
		   if (!v[y]){
		   	  v[y]=true;
		   	  heap[++size]=y;
		   	  pos[y]=size;
		   	  up(size,opt);
		   }
		}
		pos[heap[size]]=1;
		heap[1]=heap[size];
		size--;
		down(1,size,opt);
	}
}

int main(){
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	int x,y,c;
	cin>>n>>m;
	e=1;
	memset(p,0,sizeof(p));
	while(m--){
		scanf("%d%d%d",&x,&y,&c);
		add(x,y,c);
		add(y,x,c);
	}
	heap_dj(0);
	ans=d[0][n];
	heap_dj(1);
	edge=0;
    del=0;
    for(int j=2;j<=e;++j)
	if (d[0][head[j^1]]+w[j]+d[1][head[j]]==d[0][n])
    {
    	w[j]*=2;
	    w[j^1]=w[j];
	    heap_dj(2);
	    if(del<d[2][n]) del=d[2][n];
	    w[j]/=2;
	    w[j^1]=w[j];
    }
	printf("%d\n",del-ans);
	return 0;
}