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

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const long long INF=0x7FFFFFFF;
//ifstream fi("rblock.in");
//ofstream fo("rblock.out");
int N,M;
class EDGE
{
public:
	int u,v;
	long long w;
};
vector <EDGE> E;
vector <int> p[251];
int father[251]={0};
long long cost,Ans;
long long key[251]={0};
bool inq[251]={false};
deque <int> Q;
long long SPFA()
{
	memset(inq,false,sizeof(inq));
	for(int i=1;i<=N;i++)
		key[i]=INF;
	key[1]=0;
	Q.clear();
	Q.push_back(1);
	inq[1]=true;
	int a,b;
	long long l;
	while(!Q.empty())
	{
		a=Q.front();Q.pop_front();inq[a]=false;
		for(unsigned int i=0;i<p[a].size();i++)
		{
			b=E[p[a][i]].v;
			l=E[p[a][i]].w;
			if(key[b]<key[a]+l)continue;
			key[b]=key[a]+l;
			father[b]=p[a][i];
			if(inq[b])continue;
			inq[b]=true;
			Q.push_back(b);
		}
	}
	return key[N];
}
long long spfa(int change)
{
	memset(inq,false,sizeof(inq));
	for(int i=1;i<=N;i++)
		key[i]=INF;
	key[1]=0;
	Q.clear();
	Q.push_back(1);
	inq[1]=true;
	int a,b;
	long long l;
	while(!Q.empty())
	{
		a=Q.front();Q.pop_front();inq[a]=false;
		for(unsigned int i=0;i<p[a].size();i++)
		{
			b=E[p[a][i]].v;
			l=E[p[a][i]].w;
			if(p[a][i]==change || p[a][i]==(change^1))
				l<<=1;//加倍
			if(key[b]<key[a]+l)continue;
			key[b]=key[a]+l;
			if(inq[b])continue;
			inq[b]=true;
			Q.push_back(b);
		}
	}
	return key[N];
}
int main()
{
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&N,&M);
	//fi>>N>>M;
	int a,b,tot;
	long long l=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%lld",&a,&b,&l);
		//fi>>a>>b>>l;
		E.push_back((EDGE){a,b,l});
		E.push_back((EDGE){b,a,l});
		tot=E.size()-2;
		p[a].push_back(tot);
		p[b].push_back(tot+1);
	}
	cost=SPFA();
	Ans=0;
	int i=father[N];
	do
	{
		Ans=max(Ans,spfa(i));
		i=father[E[i].u];
	}while(i!=0);
	/*for(int i=father[N];E[i].u!=1;i=father[E[i].u])
	{
		Ans=max(Ans,spfa(i));
	}*/
	//fo<<Ans-cost<<endl;
	printf("%lld\n",Ans-cost);
	return 0;
}