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

#include<fstream>
#define ll long long
#define maxint 0x7fffffff
using namespace std;
ifstream fin("rblock.in");
ofstream fout("rblock.out");
ll map[251][251]={{0}},dis[251]={0},path[251]={0},road[251]={0};//path记录路径前驱，road记录路径
ll N,M,L,s,t;//s记录最短路总长度，t记录差值
ll DIJ1()
{
	int i,j;
	bool use[251]={0};
	for(i=1;i<=N;i++)
	{
		dis[i]=map[1][i];
		path[i]=1;
		use[i]=0;
	}
	dis[1]=0;use[1]=0;path[1]=0;
	for(i=1;i<=N;i++)
	{
		ll min=maxint,u=-1;
		for(j=1;j<=N;j++)
		{
			if(!use[j]&&dis[j]<min)
			{
				min=dis[j];
				u=j;
			}
		}
	    use[u]=1;
		for(j=1;j<=N;j++)
		{
			if(!use[j]&&dis[j]>dis[u]+map[u][j])
			{
				dis[j]=dis[u]+map[u][j];
				path[j]=u;
			}
		}
	}
	ll sum=1,e=N;
	while(e!=1)
	{
		road[sum]=e;
		sum++;
		e=path[e];
	}
	road[sum]=1;
	L=sum;
	return dis[N];
}
ll DIJ2()
{
	int i,j;
	bool use[251]={0};
	for(i=1;i<=N;i++)
	{
		dis[i]=map[1][i];
		use[i]=0;
	}
	dis[1]=0;use[1]=0;
	for(i=1;i<=N;i++)
	{
		ll min=maxint,u=-1;
		for(j=1;j<=N;j++)
		{
			if(!use[j]&&dis[j]<min)
			{
				min=dis[j];
				u=j;
			}
		}
	    use[u]=1;
		for(j=1;j<=N;j++)
		{
			if(!use[j]&&dis[j]>dis[u]+map[u][j]) dis[j]=dis[u]+map[u][j];
		}
	}
	return dis[N];
}
int main()
{
	fin>>N>>M;
	ll i,j,a,b,c;
	for(i=1;i<=N;i++) for(j=1;j<=N;j++) map[i][j]=maxint;
	for(i=1;i<=M;i++)
	{
		fin>>a>>b>>c;
		map[a][b]=map[b][a]=c;
	}
	s=DIJ1();
	for(i=1;i<L;i++)
	{
		map[road[i]][road[i+1]]*=2;
		map[road[i+1]][road[i]]*=2;
		t=max(t,DIJ2()-s);
		map[road[i]][road[i+1]]/=2;
		map[road[i+1]][road[i]]/=2;
	}
	fout<<t<<endl;
    return 0;
}