POJ 1125-Stockbroker Grapevine

題意： n個人炒股，每個人都可以給其他人報信，第 1 行 n，第x行 第一個 是 第 x-1個人可以給幾個人報信，和時間 球最少時間 和從第幾個人開始報信

水題，Floyd 一遍 過；

ME 676KB

TI 16MS

#include 
#include 
#include 
#include 
#include 
#include 
const int INF = 1e7;
const int N = 105;
using namespace std;
int mapp[N][N],n;
void init()
{
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
            {
                mapp[i][j] = INF;
            }
    }
}
void Floyd()
{
    int k,j,i;
    for(k = 1;k<=n;k++)
    {
        for(i = 1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(mapp[i][j] > mapp[i][k] + mapp[k][j])
                    mapp[i][j] = mapp[k][j] + mapp[i][k];
            }
        }
    }
}
int main()
{
    int s,wz,ti;
    while(scanf(%d,&n),n)
    {
        init();
        for(int i = 1;i<=n;i++)
        {
            scanf(%d,&s);
            for(int j = 1;j<=s;j++)
            {
                scanf(%d%d,&wz,&ti);
                mapp[i][wz] = ti;
            }
        }
        Floyd();
        int st = -1,maxx = 0,ti = INF;
        for(int i = 1;i<=n;i++)
        {
            maxx = 0;
            for(int j = 1;j<=n;j++)
            {
                if(i==j)
                    continue;
                if(mapp[i][j]> maxx)
                {
                    maxx = mapp[i][j];
                }
            }
            if(ti>maxx)
            {
                ti = maxx;
                st = i;
            }
        }
        if(st!=-1)
            printf(%d %d
,st,ti);
            else
                puts(disjoint);
    }
    return 0;
}