题目地址：
题解：题目意思为从起点到终点的最短路中有一条路不能通过了，求到从起点到终点的最短距离。
可以先找出从起点到终点的最短距离，并将路径保存下来，然后枚举最短路径中的所有路径，求
出从起点到终点的最短路径中最长的一条。
#include<iostream>
#include<string>
#include<queue>
using namespace std;
const int maxn = 1005;
const int INF = 200000000;
struct node
{
int v,t;
struct node *next;
}*head[maxn],edge[maxn*maxn];
int n,m,dis[maxn],per[maxn];
bool vis[maxn];
queue<int> que;
void spfa()
{
for(int j = 1; j <= n; j++)
dis[j] = INF,vis[j] = false;;
dis[1] = 0;vis[1] = true;
que.push(1);
while(!que.empty())
{
int now = que.front();
que.pop();
vis[now] = false;
for(node *p = head[now] ; p ; p = p->next)
{
if(dis[p->v] > dis[now] + p->t)
{
dis[p->v] = dis[now] + p->t;
per[p->v] = now;//记录到点p->的前驱结点
if(!vis[p->v])
{
vis[p->v] = true;
que.push(p->v);
}
}
}
}
}
void spfa(int x,int y)
{
for(int i = 1; i <= n; i++)
dis[i] = INF,vis[i] = false;
vis[1] = true;
dis[1] = 0;
que.push(1);
while(!que.empty())
{
int now = que.front();
que.pop();
vis[now] = false;
for(node *p = head[now] ; p ; p = p->next)
{
if((now == y && p->v == x)||(now == x && p->v == y))//路p->v到now的路不能走
continue;
if( dis[p->v] > dis[now] + p->t)
{
dis[p->v] = dis[now] + p->t;
if(!vis[p->v])
{
vis[p->v] = true;
que.push(p->v);
}
}
}
}
}
int main()
{
int i;
int a,b,time;
while(cin >> n >> m)
{
for(i = 1; i <= n; i++)
head[i] = NULL;
node *p = edge;
while(m --)
{
cin >> a >> b >> time;
p->v = b;p->t = time;
p->next = head[a];
head[a] = p++;
p->v = a; p->t = time;
p->next = head[b];
head[b] = p++;
}
per[1] = -1;
spfa();
int max = dis[n];
for(i = n; per[i] != -1; i = per[i])//枚举最短路中的所有路径。
{
spfa(i,per[i]);
if(dis[n] != INF && dis[n] > max)
max = dis[n];
}
printf("%d\n",max);
}
return 0;
}