记录编号	96614	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]路障	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2014-04-14 11:51:29	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define INF 4000000000
using namespace std;
const int MAXN=250+10;
typedef long long LL;
vector<int>used;
struct Edge{int from,to,dist;};
struct BellmanFord
{
	int n,m;
	vector<Edge>edges;
	vector<int>g[MAXN];
	bool entered[MAXN];
	LL d[MAXN];
	int cnt[MAXN],p[MAXN];
	void INITIALIZE(int n)
	{
		this->n=n;
		for(int i=1;i<=n;i++)g[i].clear();
		edges.clear();
	}
	void ADD(int from,int to,int dist)
	{
		edges.push_back((Edge){from,to,dist});
		m=edges.size();
		g[from].push_back(m-1);
	}
	bool SORT(int s)
	{
		queue<int>q;
		memset(entered,0,sizeof(entered));
		memset(cnt,0,sizeof(cnt));
		int i,j,u;
		for(i=1;i<=n;i++)d[i]=INF;
		d[s]=0;
		q.push(s);
		entered[s]=true;
		while(!q.empty())
		{
			u=q.front();q.pop();
			entered[u]=false;
			for(i=0;i<g[u].size();i++)
			{
				Edge& e=edges[g[u][i]];
				if(d[e.to]>d[u]+e.dist)
				{
					d[e.to]=d[u]+e.dist;
					p[e.to]=g[u][i];					
					if(not entered[e.to])
					{
						q.push(e.to);
						entered[e.to]=true;
						if(++cnt[e.to]>n)return true;
					}
				}
			}
		}
		return false;
	}
	void DFS(int v)
	{
		if(v!=1)
		{
			DFS(edges[p[v]].from);
			used.push_back(p[v]);
		}
	}
};
BellmanFord MINPATH; 
int N,M,A,B,D,i;
LL last,now,ans;
int main()
{
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&N,&M);
	MINPATH.INITIALIZE(N);
	for(i=1;i<=M;i++)
	{
		scanf("%d%d%d",&A,&B,&D);
		MINPATH.ADD(A,B,D);
              MINPATH.ADD(B,A,D);
	}
	MINPATH.SORT(1);
	last=MINPATH.d[N];
	MINPATH.DFS(N);
	for(i=0;i<used.size();i++)
	{
		MINPATH.edges[used[i]].dist*=2;
		MINPATH.SORT(1);
		now=MINPATH.d[N];
		if(now-last>ans)
			ans=now-last;
		MINPATH.edges[used[i]].dist/=2;
	}
	cout<<ans<<endl;
	return 0;
}