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

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 255
#define MM 55000
using namespace std;

struct arr{
	int x,k;
}a[NN];

int w[MM],ff[MM],ver[MM],next[MM],head[NN],dis[NN],h[MM<<1],front[NN];
int p,n,m,tot,ans,tem,temp;

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

void up(int i){
	for (int pp = i>>1; pp; pp = i>>1){
		if (dis[h[i]] < dis[h[pp]]) swap(h[i],h[pp]);
		else return;
		i = pp;
	}
}

void down(int i){
	for (int pp = i<<1; pp <= p; pp = i<<1){
		if (dis[h[pp+1]] < dis[h[pp]] && pp < p) pp++;
		if (dis[h[pp]] < dis[h[i]]) swap(h[pp],h[i]);
		else return;
		i = pp;
	}
}

void dijis(){
	int j,x;
	memset(dis,INF,sizeof(dis));
	dis[1] = 0;
	p = 1;
	h[1] = 1;
	while (p){
		if (h[1] == n) return;
		x = h[1];
		h[1] = h[p];
		p--;
		down(1);
		for (j = head[x]; j; j = next[j]){
			if (dis[ver[j]] > dis[x]+w[j]){
				dis[ver[j]] = dis[x]+w[j];
				front[ver[j]] = j;
				h[++p] = ver[j];
				up(p);
			}
		}
	}
}

bool comp(const arr &a,const arr &b){
	return a.k<b.k;
}

int main(){
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for (i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	dijis();
	temp = dis[n];
	tot = 0;
	for (i = front[n]; ff[i]; i = front[ff[i]]){
		a[++tot].x = i;
		a[tot].k = w[i];
	}
	sort(a+1,a+tot+1,comp);
	for (i = tot; i > 0; i--){
		if (a[i].k <= ans) break;
		w[a[i].x] = w[a[i].x]<<1;
		dijis();
		w[a[i].x] = a[i].k;
		ans = max(ans,dis[n]-temp);
	}
	printf("%d\n",ans);
	return 0;
}