记录编号	96594	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]路障	最终得分	100
用户昵称	Miku_lyt	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2014-04-14 11:44:28	内存使用	1.22 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct edge{
  int x,y,l,next;
};
  
  edge v[50050];
  int d[3000];
  int d1[3000],d2[3000];
  int head[3000];
  int heap[30000];
  bool f[3000];
  int st;
  int ed;
  int tot=0;
  int n,m;
  int x,y,l;
  int top=0;

void add(int x,int y,int l){
  tot++;
  v[tot].x=x;
  v[tot].y=y;
  v[tot].l=l;
  v[tot].next=head[x];
  head[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 dijs(){
  memset(d,0x3f3f3f3f,sizeof(d));
  memset(f,0,sizeof(f));
  top=1;
  d[st]=0;
  heap[1]=st;
  int now=0;
  while (top){
    now=heap[1];
    heap[1]=heap[top];
    top--;
    down(1);
    if (f[now]){
      continue;
    }
    f[now]=1;
    for (int x=head[now];x;x=v[x].next){
      if (d[v[x].y]>d[now]+v[x].l){
        d[v[x].y]=d[now]+v[x].l;
        top++;
        heap[top]=v[x].y;
        up(top);
   
      }
    }
  }
}

int main(){
  freopen("rblock.in","r",stdin);
  freopen("rblock.out","w",stdout);
  
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&l);
    add(x,y,l);
    add(y,x,l);
  }
  
  st=n;
  ed=1;
  dijs();
  for (int i=1;i<=n;i++){
    d2[i]=d[i];
  }
  st=1;
  ed=n;
  dijs();
  for (int i=1;i<=n;i++){
    d1[i]=d[i];
  }
  
  int LLL=d[n];
  int ans=0;
  for (int i=1;i<=tot;i++){
    if (d1[v[i].x]+v[i].l+d2[v[i].y]==LLL){
      v[i].l<<=1;
      dijs();
      ans=max(ans,d[n]-LLL);
      v[i].l>>=1;
    }
  }
    
  printf("%d\n",ans);
    
  return 0;
}