最短路poj 1125

刺骨的言语ヽ痛彻心扉 2022-08-27 15:54 147阅读 0赞

题目：[poj1125**Stockbroker Grapevine**][poj1125_Stockbroker Grapevine]

题意：此题题意远比题目难

首先，题目可能有多组测试数据，每个测试数据的第一行为经纪人数量N（当N=0时，输入数据结束），然后接下来N行描述第i（1<=i<=N）个经纪人与其他经纪人的关系（教你如何画图）。每行开头数字M为该行对应的经纪人有多少个经纪人朋友（该节点的出度，可以为0），然后紧接着M对整数，每对整数表示成a,b,则表明该经纪人向第a个经纪人传递信息需要b单位时间（即第i号结点到第a号结点的孤长为b），整张图为有向图，即弧Vij 可能不等于弧Vji（数据很明显，这里是废话）。当构图完毕后，求当从该图中某点出发，将“消息”传播到整个经纪人网络的最小时间，输出这个经纪人号和最小时间。最小时间的判定方式为——从这个经纪人（结点）出发，整个经纪人网络中最后一个人接到消息的时。如果有一个或一个以上经纪人无论如何无法收到消息，输出“disjoint”（有关图的连通性，你们懂得，但据其他同学说，POJ测试数据中不会有，就是说，你不判定，一样能过，题目数据够水的）。

分析：说的很清楚了，最短路算法基本都能水过，可以选熟悉的用

强调：floyd算法用前一定初始化为INF，否则会很惨。

代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #define max(a,b) a>b?a:b
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 110;
    int map[N][N];
    int dis[N][N];
    int n;
    void Floyd()
    {
        memset(map,inf,sizeof(map));
        for(int i=1; i<=n; i++)
        {
            int t,x,s;
            scanf("%d",&t);
            while(t--)
            {
                scanf("%d%d",&x,&s);
                map[i][x]=s;
            }
        }
        for(int t=1; t<=n; t++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    map[i][j]=min(map[i][j],map[i][t]+map[t][j]);
    }
    int main()
    {
        while(~scanf("%d",&n) && n)
        {
            Floyd();
            int ans=0x3f3f3f3f,time;
            for(int i=1;i<=n;i++)
            {
                int tmp=0;
                for(int j=1;j<=n;j++)
                {
                    if(i==j)
                        continue;
                    if(map[i][j]>tmp)
                        tmp=map[i][j];
                }
                if(ans>tmp){
                    ans=tmp;
                    time=i;
                }
            }
            printf("%d %d\n",time,ans);
        }
        return 0;
    }

[poj1125_Stockbroker Grapevine]: http://poj.org/problem?id=1125