记录编号	96637	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]路障	最终得分	100
用户昵称	◆半城烟沙灬為你打天下	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-04-14 12:03:15	内存使用	1.35 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
struct sky
{
	int ff,tt,ww,next;
};
sky c[50050];
int d[5000],d1[5000],d2[5000],heap[5000],r[50050];
bool v[5000];
int m,n,tot,st,ed,ans;
int top=0,x,y,z;
void add(int x,int y,int w)
{
	tot++;
	c[tot].ff=x;
	c[tot].tt=y;
	c[tot].ww=w;
	c[tot].next=r[x];
	r[x]=tot;
}

void up(int x)
{
	while (x>>1)
	{
    	if (d[heap[x]]<d[heap[x>>1]])
		{
      		swap(heap[x],heap[x>>1]);
      		x>>=1;
      	}
    	else
		{
      		return;
    	}
  	}
}
void down(int x)
{
	int p=x<<1;
  	while (p<=top)
	{
		if (p<top&&d[heap[p]]>d[heap[p+1]])
		{
			p++;
    	}
    	if (d[heap[x]]>d[heap[p]])
		{
      		swap(heap[x],heap[p]);
      		x=p;
      		p=x<<1;
    	}
    	else
		{
      		return;
    	}
  	}
}
void DJ()
{
	memset(d,0x3f3f3f3f,sizeof(d));
  	memset(v,0,sizeof(v));
  	top=1;
  	d[st]=0;
  	heap[1]=st;
  	v[st]=1;
  	int now=0;
  	while (top)
	{
		now=heap[1];
    	heap[1]=heap[top];
    	top--;
    	down(1);
    	for (int x=r[now];x;x=c[x].next)
		{
			if (d[c[x].tt]>d[now]+c[x].ww)
			{
				d[c[x].tt]=d[now]+c[x].ww;
        		if (!v[c[x].tt])
				{
          			top++;
          			heap[top]=c[x].tt;
          			up(top);
        		}       
      		}
    	}
  	}
}
int main()
{
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&n,&m);
	tot=1;
	memset(r,0,sizeof(r));
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	st=n;ed=1;
	DJ();
	for (int i=1;i<=n;i++)
	{
		d2[i]=d[i];
	}
	st=1;ed=n;
	DJ();
	for (int i=1;i<=n;i++)
	{
    	d1[i]=d[i];
    }
	ans=0;int a=d[n];
	for (int i=1;i<=tot;i++)
	{
    	if (d1[c[i].ff]+c[i].ww+d2[c[i].tt]==a)
		{
      		c[i].ww<<=1;
      		c[i^1].ww<<=1;
      		DJ();
      		ans=max(ans,d[n]-a);
      		c[i].ww>>=1;
      		c[i^1].ww>>=1;
    	}
  	}
	printf("%d\n",ans);
}