/*
分析:
真不明白,同样的方法,用SPFA写的WA了,用
Dij写ac了,还234MS,第三,ac的。。。而且~~~~
另外一道几乎一样的题目,用同样的SPFA,也ac了!
不管那么多了,ac了,可以泪奔了~
先求最短路,然后枚举最短路上的边,一个一个
的删除、求最短路、安上。。。求得的最大的最短路
就是答案。
2012-07-28 16:47
*/
#include"stdio.h" #include"string.h" #include"queue" using namespace std; int n,m; struct A { int dis; int pre; int pre_len; int flag; int tot; int mem[1011]; int len[1011]; }E[1011]; struct node { int num; int dis; friend bool operator<(node n1,node n2) { return n2.dis<n1.dis; } }; int Dij() { priority_queue<node>q; node cur,next; int i; int temp; cur.num=1; cur.dis=0; q.push(cur); while(!q.empty()) { cur=q.top(); q.pop(); if(!E[cur.num].flag) continue; E[cur.num].flag=0; if(cur.dis>=E[n].dis) break; for(i=0;i<E[cur.num].tot;i++) { temp=E[cur.num].mem[i]; if(E[cur.num].dis+E[cur.num].len[i]<E[temp].dis) { E[temp].dis=E[cur.num].dis+E[cur.num].len[i]; E[temp].pre=cur.num; E[temp].pre_len=E[cur.num].len[i]; next.num=temp; next.dis=E[temp].dis; q.push(next); } } } return E[n].dis; } int main() { int i,l; int z; int a,b,c; int ans; int des[1011],des2[1011],k,temp,len; while(scanf("%d%d",&n,&m)!=-1) { for(i=1;i<=n;i++) E[i].tot=0; while(m--) { scanf("%d%d%d",&a,&b,&c); E[a].mem[E[a].tot]=b; E[b].mem[E[b].tot]=a; E[a].len[E[a].tot++]=c; E[b].len[E[b].tot++]=c; } for(i=1;i<=n;i++) {E[i].pre=i;E[i].dis=1111111111;E[i].flag=1;} E[1].dis=0; temp=Dij(); k=0; temp=n; while(E[temp].pre!=temp) { des[k]=temp; des2[k++]=E[temp].pre_len; temp=E[temp].pre; } des[k++]=temp; ans=-1; for(z=0;z<k-1;z++) { a=des[z]; b=des[z+1]; len=des2[z]; for(l=0;l<E[a].tot;l++) if(E[a].mem[l]==b && E[a].len[l]==len) break; for(;l<E[a].tot-1;l++) {E[a].mem[l]=E[a].mem[l+1];E[a].len[l]=E[a].len[l+1];} E[a].tot--; for(l=0;l<E[b].tot;l++) if(E[b].mem[l]==a && E[b].len[l]==len) break; for(;l<E[b].tot-1;l++) {E[b].mem[l]=E[b].mem[l+1];E[b].len[l]=E[b].len[l+1];} E[b].tot--; for(i=1;i<=n;i++) {E[i].dis=1111111111;E[i].flag=1;} E[1].dis=0; temp=Dij(); if(temp>ans) ans=temp; E[a].mem[E[a].tot]=b; E[b].mem[E[b].tot]=a; E[a].len[E[a].tot++]=len; E[b].len[E[b].tot++]=len; } printf("%d\n",ans); } return 0; }