poj 1125 Stockbroker Grapevine

 

解题思路

题意：

   每个stockbroker同一时间可以向多个人发消息。求的是从哪个stockbroker开始发消息，直到所有人都收到消息，时间花的最短，并求出最短时间。

 

思路：

   用Floyd或者dijkstra都可以做，我用的是后者，枚举每个节点，用单纯的dijkstra算法，没做修改，最后找出最小值。数据比较水，我忘记了处理非连通图的情况，即没用到disjoint也过了。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 101
#define inf 0xffffff

int g[N][N];


//单纯的dij
int dijkstra(int v, int n)
{
    int min, minid, i, j;
    int dis[N], mark[N];

    for(i=1; i<=n; i++)
    {
        dis[i] = g[v][i];
        mark[i] = 0;
    }
    mark[v] = 1;
    for(i=1; i<n; i++)
    {
        min = inf;
        minid = 0;
        
        for(j=1; j<=n; j++)
        {
            if(!mark[j] && dis[j] < min)
            {
                min = dis[j];
                minid = j;
            }
        }

        if(!minid)
            break;
        mark[minid] = 1;
        for(j=1; j<=n; j++)
        {
            if(!mark[j] && min + g[minid][j] < dis[j])
                dis[j] = min + g[minid][j];
        }
    }
    return min;
}

int main()
{
    int i, j;
    int n, m, min, minid, time, x;
    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                g[i][j] = inf;

        for(i=1; i<=n; i++)
        {
            scanf("%d", &m);
            for(j=1; j<=m; j++)
            {
                scanf("%d", &x);
                scanf("%d", &g[i][x]);
            }
        }
        min = dijkstra(1, n);
        minid = 1;

       //枚举每个顶点用dijkstra，求出最小值
        for(i=2; i<=n; i++)
        {
            time = dijkstra(i, n);
            if(time < min)
            {
                min = time;
                minid = i;
            }
        }
        printf("%d %d\n", minid, min);
    }
    getch();
    return 0;
}