HDU 5137 How Many Maos Does the Guanxi Worth（枚举+最短路径）

本文主要是介绍HDU 5137 How Many Maos Does the Guanxi Worth（枚举+最短路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：点击打开链接

题意：给出一个无向图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;}
}