分布式集群消息传递

import java.util.*;

// Dijkstra：单源最短路径
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.next();
        int n = in.nextInt(), k = in.nextInt();
        List<List<int[]>> g = new ArrayList<>(); // 邻接表
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        line = line.substring(2, line.length() - 2); // 处理输入
        String[] sp = line.split("\\],\\["); // 去掉首尾[[ ]], 中间可以用],[分割
        for (String str : sp) {
            String[] spp =  str.split(",");
            int s = Integer.parseInt(spp[0]);
            int d = Integer.parseInt(spp[1]);
            int t = Integer.parseInt(spp[2]);
            g.get(s).add(new int[] {d, t}); // 有向图
            // g.get(d).add(new int[] {s, t});
        }

        int[] dist = new int[n + 1]; // k点到其他点的距离
        int INF = Integer.MAX_VALUE >> 1;
        Arrays.fill(dist, INF);
        dist[k] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->a[1] - b[1]);
        queue.offer(new int[] {k, 0});
        while (!queue.isEmpty()) {
            int[] a = queue.poll();
            int s = a[0], dis = a[1];
            if (dis > dist[s]) continue;

            for (int[] b : g.get(s)) {
                int d = b[0], t = b[1];
                int newDis = dis + t;
                if (newDis < dist[d]) {
                    dist[d] = newDis;
                    b[1] = newDis;
                    queue.offer(b);
                }
            }
        }

        int max = -1;
        for (int i = 1; i <= n; i++) { // k到其他点的最长距离
            if (dist[i] == INF) {
                max = -1;
                break;
            }
            max = Math.max(dist[i], max);
        }
        System.out.println(max);
    }
}