题目：点击打开链接
题意：给出一个无向图n个点m条边，断开其中的除了1和n之外的其中一个点的所有边，让最短路最长。
思路：依次枚举除了1和n之外的其中一个点的所有边的最短路的结果，并且求出最大值。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 35;
int mp[maxn][maxn],vis[maxn],lowcost[maxn],tmp[maxn];
int n,m;
int dijstra(){
memset(vis,0,sizeof(vis));
vis[1]=1;
for(int i=1; i<=n; i++)
lowcost[i]=mp[1][i];
lowcost[1]=0;///注意赋值为0 否则会出错
for(int i=1; i<n; i++){
int mi=INF,flag;
for(int j=1; j<=n; j++){
if(!vis[j]&&lowcost[j]<mi){
mi=lowcost[j];
flag=j;
}
}
vis[flag]=1;
for(int j=1; j<=n; j++){///更新
if(!vis[j]&&lowcost[j]>lowcost[flag]+mp[flag][j])
lowcost[j]=lowcost[flag]+mp[j][flag];
}
///if(flag==n) break;
}
return lowcost[n];
}
int main(){
while(cin>>n>>m){
if(n==0&&m==0) break;
for(int i=1; i<=n; i++)///初始化
for(int j=1; j<=n; j++)
mp[i][j]=INF;
int a,b,c;
for(int i=0; i<m; i++){
cin>>a>>b>>c;
mp[a][b]=mp[b][a]=c;
}
int ans=0;
for(int i=2; i<n; i++){
for(int j=1; j<=n; j++){///依次切断i点与所有点的联系，并暂时保存这些值，以便随后恢复
tmp[j]=mp[i][j];
mp[i][j]=mp[j][i]=INF;
}
ans=max(ans,dijstra());
for(int j=1; j<=n; j++)///恢复i与所有点的初始值
mp[i][j]=mp[j][i]=tmp[j];
}
if(ans==INF) cout<<"Inf"<<endl;
else cout<<ans<<endl;
}
}
奇怪的是跑第二组测试数据有时候会崩溃，但是居然AC，应该数据比较水，找了几天的bug没找出来，麻烦大家看看，如果发现什么问题可以直接指出来，谢谢！
