首页 > 代码库 > 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,否则会很惨。

Sample Input

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

Sample Output

3 2
3 10
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;
int T;
//int i,j,k;
int inf=50;





int e[500][500];

void floyd(){
    for(int j=1;j<=T;j++){
        for(int k=1;k<=T;k++){
            for(int i=1;i<=T;i++){
                if(k!=i&&e[k][i]>e[k][j]+e[j][i])
                    e[k][i]=e[k][j]+e[j][i];     //经典五行弗洛伊德算法
            }
        }
    }
    int maxl;
    int minl=inf;
    int flag;
    for(int i=1;i<=T;i++){
        maxl=0;
        for(int j=1;j<=T;j++){
            if(i!=j&&maxl<e[i][j])
                maxl=e[i][j];
        }

        if(maxl<minl){
            minl=maxl;
            flag=i;     //选出最短的时间和编号


            }
        }
    cout<<flag<<" "<<minl<<endl;
}
int main(){

    while(1)
    {memset(e,inf,sizeof(e));
    cin>>T;
    if(!T) break;
    /*for(i=0;i<500;i++)
        for(j=0;j<500;j++){
        //if(i==j) e[i][j]=0;
        //else e[i][j]=inf;
        e[i][j]=inf;
        }*/

    for(int k=1;k<=T;k++){
        int m;
        cin>>m;
        for(int i=1;i<=m;i++){
            int t,v;
            cin>>t>>v;
            e[k][t]=v;
        }

    }

    floyd();
    }


    return 0;
}

 

poj1125 Stockbroker Grapevine