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

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int n,m;
int fro[60000],ver[60000],next[60000],r[300],tot;
int w[60000];
int dis1[300],dis2[300],dis3[300];
int pre[300];
int ans1,ans2;
bool v[300];


void add(int x,int y,int z){
	ver[++tot]=y;
	fro[tot]=x;
	w[tot]=z;
	next[tot]=r[x];
	r[x]=tot;
}

void init(){
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	tot=1;
	memset(r,0,sizeof(r));
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
}

void dijkstra1(){
	int i,y,j,k;
	long long temp;
	memset(v,0,sizeof(v));
	memset(dis1,0x3f3f3f3f,sizeof(dis1));
	dis1[1]=0;
	for (i=1;i<=n;i++){
		temp=0x3f3f3f3f;
		for (j=1;j<=n;j++)
		if (dis1[j]<temp && !v[j]){
			temp=dis1[j];
			k=j;
		}
		v[k]=true;
		for (j=r[k];j;j=next[j]){
			y=ver[j];
			if (dis1[y]>dis1[k]+w[j]){
				dis1[y]=dis1[k]+w[j];
				pre[y]=j;
			}
		}
	}
	ans1=dis1[n];
}
		
void dijkstra2(){
	int i,y,j,k;
	long long temp;
	memset(v,0,sizeof(v));
	memset(dis2,0x3f3f3f3f,sizeof(dis2));
	dis2[n]=0;
	for (i=1;i<=n;i++){
		temp=0x3f3f3f3f;
		for (j=1;j<=n;j++)
		if (dis2[j]<temp && !v[j]){
			temp=dis2[j];
			k=j;
		}
		v[k]=true;
		for (j=r[k];j;j=next[j]){
			y=ver[j];
			if (dis2[y]>dis2[k]+w[j])
				dis2[y]=dis2[k]+w[j];
		}
	}
}
void dijkstra3(){
	int i,y,j,k;
	long long temp;
	memset(v,0,sizeof(v));
	memset(dis3,0x3f3f3f3f,sizeof(dis3));
	dis3[1]=0;
	for (i=1;i<=n;i++){
		temp=0x3f3f3f3f;
		for (j=1;j<=n;j++)
		if (dis3[j]<temp && !v[j]){
			temp=dis3[j];
			k=j;
		}
		v[k]=true;
		for (j=r[k];j;j=next[j]){
			y=ver[j];
			if (dis3[y]>dis3[k]+w[j]){
				dis3[y]=dis3[k]+w[j];
				pre[y]=j;
			}
		}
	}
}
	
void solve(){
	int i,x,y,j;
	long long temp;
	ans2=0;
	for (i=pre[n];i;i=pre[fro[i]]){
		w[i]=w[i]*2;
		dijkstra3();
		ans2=max(ans2,dis3[n]-ans1);
		w[i]=w[i]/2;
	}
	printf("%d\n",ans2);
}
	
int main(){
freopen("rblock.in","r",stdin);
freopen("rblock.out","w",stdout);
	init();
	dijkstra1();
	dijkstra2();
	solve();
	
	return 0;
}