无需去重边，链式前向星存图，SPFA求两点间最短路，Java实现

无需去重边，链式前向星存图，spfa求两点间最短路

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        int t = sc.nextInt();
        Graph graph = new Graph(n, m);
        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph.add(u, v, w);
        }
        Queue<Integer> que = new LinkedList<>();
        if (s != t)
            que.add(s);
        int[] dis = new int[n+1];
        boolean[] vis = new boolean[n+1];
        for (int i = 0; i <= n; ++i)
            dis[i] = Integer.MAX_VALUE;
        dis[s] = 0;
        vis[s] = true;
        while(!que.isEmpty()) {
            int u = que.poll();
            vis[u] = false;
            for (int i = graph.head[u]; i != -1; i = graph.edge[i].next) {
                int v = graph.edge[i].to;
                int w = graph.edge[i].weight;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    if (v == t) break;
                    if (!vis[v]) {
                        vis[v] = true;
                        que.add(v);
                    }
                }
            }
        }
        System.out.println(dis[t] == Integer.MAX_VALUE ? -1 : dis[t]);
    }
    static class Graph {
        int[] head;
        Edge[] edge;
        int tot = 0;
        Graph(int n, int m) {
            head = new int[n+1];
            for (int i = 0; i <= n; ++i)
                head[i] = -1;
            edge = new Edge[m];
        }
        void add(int u, int v, int w) {
            edge[tot] = new Edge(v, w, head[u]);
            head[u] = tot++;
        }
        class Edge {
            int to;
            int weight;
            int next;
            Edge(int t, int w, int n) {
                to = t; weight = w; next = n;
            }
        }
    }
}