hdoj 5137 How Many Maos Does the Guanxi Worth【最短路】

秒速五厘米 2022-08-05 20:57 58阅读 0赞

题目：[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]: http://acm.hdu.edu.cn/showproblem.php?pid=5137