转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题意是说任意去掉一条边之后的最短路的最长长度为多少。
顶点数为N达到1000的范围，显然枚举所有边再求最短路，复杂度为N^2*O(spfa),会超时的。
仔细想想便知，原图上求一次最短路，如果我们删掉最短路之外的边，之后的最短路还是原图的最短路，那我们只要枚举最短路上的边，然后再求最短路就行了。
最多路径上会有N条边，复杂度为N*O(spfa),1S左右AC。写的代码很囧，特别是记录最短路径上的边的时候，有许多地方可以改进，之前WA了，是因为我只删掉了单向边，因为是无向图，所以需要双向都删除，我找了两次，其实u->v，和v->u的边在前向星中的存储必然是相邻的，idx^1便是另外一条边的位置。懒得改了
/*ID:cxlove
PROB:HDU 1595
DATA:2012.4.4
HINT:最短路径+枚举最短路径上的边
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define inf 1<<30
using namespace std;
struct Node{
int u,v,w,next;
}edge[1000005];
struct EDGE{
int u,v,w,idx1,idx2;
}path[1005];
int start[1005],pre[1005],dist[1005];
int n,m,cnt,tot;
void addedge(int u,int v,int w){
edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;
edge[cnt].next=start[u];start[u]=cnt++;
}
void Init(){
int u,v,w;
cnt=0;tot=0;
memset(start,-1,sizeof(start));
memset(pre,-1,sizeof(pre));
while(m--){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
}
void spfa(){
bool flag[1005];
for(int i=1;i<=n;i++)
dist[i]=inf;
memset(flag,false,sizeof(flag));
queue<int >que;
que.push(1);
flag[1]=true;
dist[1]=0;
while(!que.empty()){
int u=que.front();
que.pop();
flag[u]=false;
for(int i=start[u];i!=-1;i=edge[i].next){
int v=edge[i].v,w=edge[i].w;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pre[v]=u;
if(!flag[v]){
flag[v]=true;
que.push(v);
}
}
}
}
}
void find_path(){
int v=n;
while(pre[v]!=-1){
path[tot].u=pre[v];
path[tot].v=v;
path[tot].w=dist[v]-dist[pre[v]];
int k=start[pre[v]];
while(edge[k].v!=v)
k=edge[k].next;
path[tot].idx1=k;
k=start[v];
while(edge[k].v!=pre[v])
k=edge[k].next;
path[tot++].idx2=k;
v=pre[v];
}
}
void slove(){
int ans=0;
for(int i=0;i<tot;i++){
int idx1=path[i].idx1,idx2=path[i].idx2;
int t1=edge[idx1].w,t2=edge[idx2].w;
edge[idx1].w=inf;edge[idx2].w=inf;
spfa();
ans=max(ans,dist[n]);
edge[idx1].w=t1;edge[idx2].w=t2;
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
Init();
spfa();;
find_path();
slove();
}
return 0;
}