POJ-Stockbroker Grapevine-Floyd算法-每一对顶点间最短路径-动态规划

题意如下：给定一个矩阵，其(i,j)元素的数值表示第i个人向第j个人发送消息所用时间，消息只能在有联系的人之间传递，同一个人可以同时向多个人发送消息。问，应该从哪个人开始发送消息，最短需要多长时间，消息能从该人传递到其他所有人？

分析：典型的Floyd算法的应用。直接运用Floyd算法，求出任两个人之间传递消息所用的最短时间；对于每一个人，求出其向其他所有人传递消息所需至少的时间；比较从每一个人开始传递消息所需的至少的时间，其最小的时间即为所求。

代码：

#include <iostream>

using namespace std;

const int MAX = 103; //最大数组大小
const int MAX_VAL = 999; //表示“无穷大”

int arr[MAX][MAX];

int min(int a, int b);
void initArr(int n);
void floyd(int n);

int main()
{
    int n;
    while(cin >> n, n != 0) {
        initArr(n);

        /*初始化*/
        for(int i = 0; i < n; i++) {
            int pairs;
            cin >> pairs;
            int no, t;
            for(int j = 0; j < pairs; j++) {
                cin >> no >> t;
                arr[i][no - 1] = t;
            }
        }

        floyd(n);

        int row;
        int minTimeOutput = MAX_VAL;
        for(int i = 0; i < n; i++) {
            int maxInRow = -1; //该row中最大的元素
            for(int j = 0; j < n; j++) {
                if(arr[i][j] > maxInRow)
                    maxInRow = arr[i][j];
            }

            /*若该行有值等于MAX_VAL，表示对应的两点不存在通路。此时，maxInRow == MAX_VAL。
             *注意，由于边的权值值大于等于0，故若两点不存在通路，则相应arr[][]元素值一定为MAX_VAL(不存在只比MAX_VAL小“一点点”的情况）。
             */
            if(maxInRow < minTimeOutput) {
                row = i;
                minTimeOutput = maxInRow; //取所有row中最小的maxInRow
            }
        }

        cout << row + 1 << " " << minTimeOutput << endl;
    }

    return 0;
}

int min(int a, int b) {
    return a < b ? a : b;
}

/*初始化arr矩阵。*/
void initArr(int n) {
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            if(j == i)
                arr[i][j] = 0;
            else
                arr[i][j] = MAX_VAL;
        }
}

/*floyd算法求任意两点间最短路径*/
void floyd(int n) {
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
}