题目描述

输入项
输入将描述连接n个处理器的网络的拓扑。输入的第一行将是n，即处理器的数量，因此1 <= n <=100。

输入的其余部分定义一个邻接矩阵A。邻接矩阵是正方形，大小为nx n。它的每个条目都是整数或字符x。A（i，j）的值表示直接从节点i向节点j发送消息的开销。A（i，j）的x值表示无法将消息直接从节点i发送到节点j。

请注意，对于节点向其自身发送消息不需要网络通信，因此对于1 <= i <= n，A（i，i）= 0。此外，您可能会假定网络是无向的（消息可以以相同的开销在任一方向上传播），因此A（i，j）= A（j，i）。因此，将仅提供A的（严格）下部三角形部分上的条目。

程序的输入将是A的下部三角形部分。也就是说，输入的第二行将包含一个条目A（2,1）。下一行将包含两个条目A（3,1）和A（3,2），依此类推。
输出量
您的程序应输出从第一个处理器向所有其他处理器广播消息所需的最短通信时间。

样本输入

5
50
30 5
100 20 50
10 xx 10

样本输出

35

算法

Dijkstra（迪杰斯特拉）算法：找到最短距离已经确定的点，从它出发更新相邻顶点的最短距离。此后不再关心前面已经确定的“最短距离已经确定的点”。

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。

初始时，集合T只有顶点s。然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

java

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Dijkstra {

    public static int[][] graph;
    //t表示已经确定了最短路的顶点集，从未确定的点里面找一个最小的,从d[]中找一个从源点(起始点)到其他顶点的最小权值的顶点
    public static int minIndex(int[] d, Set<Integer> t) {
        int index=-1;
        int max=Integer.MAX_VALUE;
        for(int i=0;i<d.length;i++) {
            //顶点i没有加到集合t中,并且源点s到顶点i之间有边
            if(!t.contains(i) && d[i]<max) {
                max=d[i];
                index=i;
            }
        }
        return index;
    }

    //求从源点(起始点)到其他以源点为直接前驱的顶点的距离。
    //d[j]表示从源点s到顶点j的距离(没有经过其他点)
    public static int[] shortestPath(int s) {
        //顶点数
        int n = graph.length;
        //记录源点s到各顶点的最短距离
        int[] d=new int[n];
        d[s]=0;     //自己到自己为0
        //记录已经找到最短距离的顶点
        Set<Integer> t=new HashSet<Integer>();
        t.add(s);

        for(int i=0;i<n;i++) {
            if(i!=s && graph[s][i]==0) {
                d[i]=Integer.MAX_VALUE;     //源点s不可达顶点i
            }
            if(i!=s && graph[s][i]>0) {     //源点s可达顶点i
                d[i]=graph[s][i];   
            }
        }

        while(t.size()<n) {
            //找到边的权值最小的下标
            int min = minIndex(d,t);
            t.add(min);
            //全部的边都加到了集合中,已经构成了最短路径
            if(t.size() == n) {
                break;
            }
            //找源点s到顶点i最短路
            for(int neighbor = 0; neighbor < n; neighbor++) {
                int cost = graph[min][neighbor];
                //更新最短路径值
                if(cost>0 && d[neighbor]>d[min]+cost) {
                    d[neighbor] = d[min] + cost;    
                }
            }
        }
        return d;       
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        graph=new int[n][n];
        graph[0][0]=0;
        for(int i=1;i<n;i++) {
            for(int j=0;j<i;j++) {
                try{
                    graph[i][j]=Integer.parseInt(sc.next());
                    graph[j][i]=graph[i][j];
                }catch (NumberFormatException e) {
                    // TODO: handle exception
                    graph[i][j]=0;
                    graph[j][i]=graph[i][j];
                }
            }
        }

        int a[]=shortestPath(0);
        int res=0;

        for(int i=0;i<a.length;i++) {
            if(a[i]>res) {      //题目要求从第一个点开始，所有的顶点都要接收到信息，即求源点s传播其他点所有
                res=a[i];       //最短时间中的最长的时间，这样所有的处理器才能都接收到信息
            }
        }
        System.out.println(res);    
    }

}