首页 > 代码库 > hdoj 5137 How Many Maos Does the Guanxi Worth【最短路】
hdoj 5137 How Many Maos Does the Guanxi Worth【最短路】
题目:hdoj 5137 How Many Maos Does the Guanxi Worth
题意:给出一个无向图n个点m条边,断开其中的除了1和n之外的其中一个点的所有边,让最短路最长。
分析:思路已经题意中给出了。枚举删去那些的所有变,然后求一个最大的最短路。就是写代码的事儿
AC代码:
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int inf = 0x3f3f3f3f; int dis[250],map[250][250]; int vis[250]; int n,m; int dij(int x,int y) { for(int i=1; i<=n; i++) dis[i]=map[x][i]; memset(vis,0,sizeof(vis)); vis[x]=1; dis[x]=0; //注意这个、开始没注意到、 int k=x; for(int i=1; i<n; i++) { int mmax=inf; for(int j=1; j<=n; j++) //每个的最短 { if(!vis[j]&&dis[j]<mmax) { mmax=dis[j]; k=j; } } vis[k]=1; for(int j=1; j<=n; j++) //更新 { if(!vis[j]&&dis[j]>dis[k]+map[k][j]) dis[j]=dis[k]+map[k][j]; } } return dis[y]; } int css[200]; int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; int a,b,v,d,f,num; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) map[i][j]=map[j][i]=inf; for(int i=0; i<m; i++) { cin>>a>>b>>v; if(map[a][b]>v) map[a][b]=map[b][a]=v; } int ans = 0; for(int i=2;i<n;i++) { for(int j=1;j<=n;j++) { css[j] = map[i][j]; map[i][j] = map[j][i] = inf; } ans = max(ans,dij(1,n)); for(int j=1;j<=n;j++) { map[i][j] = map[j][i] = css[j]; } } if(ans==inf) puts("Inf"); else printf("%d\n",ans); } return 0; }
hdoj 5137 How Many Maos Does the Guanxi Worth【最短路】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。