题解 | 【模板】单源最短路Ⅲ ‖ 非负权图

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        List<int[]>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj[u].add(new int[] {v, w});
        }

        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[s] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1],
                b[1]));
        pq.add(new long[] {s, 0});

        while (!pq.isEmpty()) {
            long[] node = pq.poll();
            int u = (int) node[0];
            long currentDist = node[1];

            if (currentDist > dist[u]) {
                continue;
            }

            for (int[] edge : adj[u]) {
                int v = edge[0];
                int w = edge[1];
                if (dist[v] > currentDist + w) {
                    dist[v] = currentDist + w;
                    pq.add(new long[] {v, dist[v]});
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i == s) {
                sb.append(0);
            } else {
                sb.append(dist[i] == Long.MAX_VALUE ? -1 : dist[i]);
            }
            if (i < n) {
                sb.append(' ');
            }
        }
        System.out.println(sb);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用BufferedReader和StringTokenizer快速读取输入数据，构建邻接表。
2. 初始化距离数组：将起点距离设为0，其余顶点设为无穷大。
3. 优先队列处理：使用优先队列存储顶点及其当前最短距离，每次取出距离最小的顶点进行处理。
4. 松弛操作：遍历当前顶点的所有出边，尝试更新目标顶点的最短距离。若更新成功，将目标顶点加入优先队列。
5. 结果输出：遍历所有顶点，输出从起点到每个顶点的最短距离。若不可达，输出-1；起点到自身的距离始终为0。