题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

算法

思路：若dist[b] = min(dist[b], dist[a] + w), 那么只有当dist[a]更新比原有值更小的时候，与a相邻点（包括 b）的距离才会更小。
因此使用队列存储距离变小的节点，用其更新其他节点
存储：数组模拟队列；邻接表存储图结构
注意：如a—>b w
e[i] 存储链接a的后续节点
ne[i] 将后续所有节点e[i]链接起来
w[i] 存放的就是此处的权重

具体代码

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

public class Main {

    private static int INF = 0x3f3f3f3f;
    private static int N = 100010;
    private static int idx = 0;
    private static int[] e = new int[N];
    private static int[] ne = new int[N];
    private static int[] h = new int[N];
    private static boolean[] st = new boolean[N]; // 标记是否访问
    private static int[] q = new int[N]; // 队列
    private static int[] w = new int[N]; // 权重
    private static int[] dist = new int[N]; // 路径权重

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        Arrays.fill(h, -1);
        Arrays.fill(dist, INF);

        for (int i=0; i<m; i++) {
            line = reader.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            int c = Integer.parseInt(line[2]);
            add(a, b, c);
        }

        int res = spfa(n);
        if (res == -1) System.out.println("impossible");
        else System.out.println(res);
    }

    private static int spfa(int n) {
        int hh = 0;
        int tt = -1;
        dist[1] = 0;
        q[++tt] = 1;
        st[1] = true;

        while (hh <= tt) {
            int t = q[hh++];
            st[t] = false;

            for (int i=h[t]; i!=-1; i=ne[i]) {
                int j = e[i];

                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q[++tt] = j;
                        st[j] = true;
                    }
                }
            }
        }

        if (dist[n] == INF) return -1; // 无法到达，则无法被更新
        return dist[n];
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}