记录编号	96722	评测结果	AAWAWWWWWA
题目名称	[USACO Feb14]路障	最终得分	40
用户昵称	Cirno	是否通过	未通过
代码语言	C++	运行时间	0.023 s
提交时间	2014-04-14 16:55:09	内存使用	0.56 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int pa[251][251]={0};//pa[x][y]为x到y的邻接矩阵
int path[251]={0};
int fin=0,num;
int bench[251]={0};
int father[251]={0};
int N,M,x,y,val,k;
int i;
int ben;
int sum=0;
int ans=0;
int fath=0;
bool view[251]={0};
void init()
{
	freopen("rblock.in","r",stdin);
	cin>>N>>M;
	for(i=1;i<=M;i++)
	{	
		cin>>x>>y>>val,pa[x][y]=val,pa[y][x]=val;
	}
}
void dij(int point,int fa)
{
	for(i=1;i<=N;i++)
	{
		if(i!=point)//不带自己
		{
			if(pa[point][i]!=0)//有边连接
			{
				if(!path[i]||path[point]+pa[point][i]<path[i])
					{father[i]=point;path[i]=path[point]+pa[point][i];}//首次发现/更新值
			}
		}
	}
	view[point]=1;
	k=0;
	for(i=1;i<=N;i++)
		if(i!=point&&view[i]==0&&path[i]!=0)
			bench[k]=i,k++;
	sort(bench,bench+k);
	for(i=k-1;i>=0;i--)
		dij(bench[i],point);
}
void dij1(int point,int fa)
{
	for(i=1;i<=N;i++)
	{
		if(i!=point)//不带自己
		{
			if(pa[point][i]!=0)//有边连接
			{
				if(!path[i]||path[point]+pa[point][i]<path[i])
					path[i]=path[point]+pa[point][i];//首次发现/更新值
			}
		}
	}
	view[point]=1;
	k=0;
	for(i=1;i<=N;i++)
		if(i!=point&&view[i]==0&&path[i]!=0)
			bench[k]=i,k++;
	sort(bench,bench+k);
	for(i=k-1;i>=0;i--)
		dij1(bench[i],point);
}
void ke()
{
	for(i=1;i<=250;i++)
		path[i]=0,view[i]=0;
	path[1]=0;
}
void findfather(int point)
{
	if(point!=1)
	{
		fath=father[point];
		pa[fath][point]*=2,pa[point][fath]*=2;
		ke();
		dij1(1,0);
		ans=max(ans,path[N]-sum);
		pa[fath][point]/=2,pa[point][fath]/=2;
	findfather(fath);
	}
	return;
}
void out()
{
	freopen("rblock.out","w",stdout);
	cout<<ans<<endl;
}
int main()
{
	init();
	path[1]=0;
	dij(1,0);
	sum=path[N];
	findfather(N);
	out();
}