算法分析

• 问题的转化：对于每个点，它接收到信的时间，等于它到指挥部的最短距离，因此只需要求1号点到所有点的最短距离的最大值

此题数据范围n = 100,m = 200
此题使用floyd,朴素Dijkstra，堆优化Dijkstra，spfa均能符合时间复杂度，下面代码使用的是floyd

时间复杂度 $O(n^3)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static int N = 110;
    static int n;
    static int m;
    static int INF = 0x3f3f3f3f;
    static int[][] d = new int[N][N];
    static void floyd()
    {
        for(int k = 1;k <= n;k ++)
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= n;j ++)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                if(i == j) d[i][j] = 0;
                else d[i][j] = INF;

        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            d[b][a] = Math.min(d[b][a], c);
            d[a][b] = Math.min(d[a][b], c);
        }
        floyd();
        int res = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(d[1][i] == INF) 
            {
                res = -1;
                break;
            }
            res = Math.max(res, d[1][i]);
        }
        System.out.println(res);
    }
}