poj1125 最短路径

问题重述
描述
众所周知，证券经纪业依靠的就是过度的传言。您需要想出股票经纪人中传播假情报的方法，让您的雇主在股票市场的占据优势。为了获得最大的效果，你必须蔓延最快的方式谣言。
不幸的是你，股票经纪人信息只信任他们的“可靠来源”，这意味着你在你传播谣言之前必须考虑到他们的接触结构。它需要特定股票经纪人和一定的时间把谣言传递给他的每一位同事。你的任务将是写一个程序，告诉您选择哪一个股票经纪人作为谣言的出发点和所花费多少时间将谣言扩散到整个社会的股票经纪人。这一期限是衡量过去的人收到信息所需的时间。
输入
你的程序包含多组股票经纪人的输入数据。每组以股票经纪人的人数开始。接下来的几行是每个经纪人与其他人接触的一些信息，包括这些人都是谁，以及将讯息传达到他们所需的时间。每个经纪人与其他人接触信息的格式如下：开头的第一个数表示共有n个联系人，接下来就有n对整数。每对整数列出的第一个数字指的是一个联系人（例如，一个'1'是指编号1的人），其次是在传递一个信息给那个人时所采取分钟的时间。没有特殊的标点符号或空格规则。
每个人的编号为1至经纪人数目。所花费的传递时间是从1到10分钟（含10分种）。股票经纪的人数范围是从1到100。当输入股票经纪人的人数为0时，程序终止。
输出
在对于每一组数据，你的程序必须输出一行，包括的信息有传输速度最快的人，谁的成果，以及早在最后一个人将会收到任何消息后，把它送给你这个人，在整数分钟计算。
你的程序可能会收到的一些关系会排除一些人，也就是有些人可能无法访问。如果你的程序检测到这样一个破碎的网络，只需输出消息“disjoint”。请注意，所花费的时间是从A传递消息到B，B传递信息到A不一定是花费同样的传递时间，但此类传播也是可能的。
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
解题过程：
分析过程：
虽然一开始就知道这是一道最短路径问题，但是对于题目的理解还是需要再细看下才行。对于最短路径，很显然有两种方法，一种是迪杰斯特拉，另外一种是弗洛依德，很显然，这道题中的Stockbrokers相互给信任他的人传递信息，形成了一张信息传递网络。而题目是要找出以谁为信息源，能使信息传播最快。故这是一个任意两点最路径问题的应用。用弗洛依德的话，效率会高一点。只要在任一Stockbroker传递信息到其他Stockbroker的最短时间的集合中，找出最大的时间，该时间就表示这一Stockbroker传递信息让其他人都知道所要花费的时间。然后在比较任一Stockbroker所花费的时间，找出最少的，就是所要求的信息源和最少花费时间。至于数据的存储，就用邻接矩阵，只要对矩阵上的时间进行修改就行了，相对比较方便。
编程过程：
这道题理解题意后就不难了。代码的编写也比较容易。只是初始化和单个顶点的环注意下就行了
做题收获：
对求最短路径的掌握更熟练了。
4.程序源码：

package middle;


import java.io.BufferedInputStream;
import java.util.Scanner;


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 * 求最短路径
 * 有两种方法。用弗洛德相对简单点
 * 这道题理解题意后就不难了。代码的编写也比较容易。
 * 只是初始化和单个顶点的环注意下就行了
 * poj1125
 * @author NC
 */
public class Poj1125 {

    final static int disjoint = 1000;//最多100个人，每个人最多花费10分钟

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        while (scan.hasNext()) {
            int n = scan.nextInt();
            if (n == 0) {
                break;
            }
            //初始化矩阵,默认不可达,stockbroker的编号是从1开始的
            int[][] times = new int[n + 1][n + 1];
            for (int i = 0; i < n + 1; i++) {
                for (int j = 0; j < n + 1; j++) {
                    times[i][j] = disjoint;
                }
            }
            for (int i = 1; i <= n; i++) {
                int stockbroker = i;
                int number = scan.nextInt();
                for (int j = 1; j <= number; j++) {
                    int contact = scan.nextInt();
                    int time = scan.nextInt();
                    times[stockbroker][contact] = time;
                }
            }
            //弗洛依德算法，顶点i到j经过k点
            for (int k = 1; k <= n; k++) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (i != j && times[i][k] + times[k][j] < times[i][j]) {
                            times[i][j] = times[i][k] + times[k][j];
                        }
                    }
                }
            }
            //注意，单个顶点本身不应该有环,这里是无穷大
            //求每个经纪人将信息传递给所有人知道所要花费的时间,存储在第0列
            for (int i = 1; i <= n; i++) {
                times[i][0] = 0;//赋0方便比较大小
                for (int j = 1; j <= n; j++) {
                    if (times[i][j] > times[i][0] && i != j) {//求max
                        times[i][0] = times[i][j];
                    }
                }
            }
            //找出最小耗时,存在第0行第0列
            int index = 0;
            for (int i = 1; i <= n; i++) {
                if (times[i][0] < times[0][0] && times[i][0] != disjoint) {//求min
                    times[0][0] = times[i][0];
                    index = i;
                }
            }
            //输出结果
            if (index == 0) {
                System.out.println("disjoint");
            } else {
                System.out.println(index + " " + times[0][0]);
            }
        }
    }
}