卡码网：94.城市间货物运输I（不存在负权回路）

思考背景：

在Bellman_ford算法中，每次松弛 都是对所有边进行松弛。但真正有效的松弛，是基于已经计算过的节点再做的松弛。

在上图中，对所有边进行松弛。但是真正有效的松弛，只有松弛 边（节点1->节点2） 和 边（节点-> 节点3）。而松弛其它的边，比如 边（节点4->节点6） ，边（节点5->节点3）等等都是无效的操作，因为节点4和节点5都是没有被计算过的节点，minDist[4] = max，minDist[5] = max。

只需要对 上一次松弛的时候更新过的节点作为出发点所连接的边 进行松弛就足够了。

所以，可以使用 队列 来记录 上次松弛的时候更新过节点。

同时，我们在将节点加入队列的过程可以有一个优化，防止重复加入相同节点进入队列。用visited数组记录节点是否已经存在在队列里，已经在队列的元素不用重复加入。

完整代码：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //存储 图，采用邻接表存储
        //邻接表可以从边的角度快速知道每个节点 所有链接的点
        List<List<Edge>> grid = new ArrayList<>(n + 1);
        //初始化 邻接表
        for(int i = 0; i <= n; i++){
            grid.add(new ArrayList<>());
        }
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            int v = scanner.nextInt();
            grid.get(s).add(new Edge(s, t, v));
        }
        //minDist数组
        int[] minDist = new int[n + 1];
        for(int i = 0; i < minDist.length; i++){
            minDist[i] = Integer.MAX_VALUE;
        }
        //节点1 就是源点，所以节点1距离源点距离要设置为0
        minDist[1] = 0;
        //标记该节点 是否加入到 队列中，防止队列重复加入相同节点
        boolean[] visited = new boolean[n + 1];
        //队列 存放 上次松弛的时候更新过的节点
        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);
        //开始算法
        //bellman_ford 松弛n-1次
            while(!q.isEmpty()){
                Integer from = q.poll();
                //该节点已经从栈中弹出，所以对应的标记就要赋值为false
                visited[from] = false;
                List<Edge> edges = grid.get(from);
                for(Edge edge : edges){
                    if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.to]){
                        minDist[edge.to] = minDist[edge.from] + edge.val;
                        if(visited[edge.to] == false){
                            q.add(edge.to);
                            visited[edge.to] = true;
                        }
                    }
                }
            }
 
        //输出结果
        if(minDist[n] == Integer.MAX_VALUE){
            System.out.print("unconnected");
        }else{
            System.out.print(minDist[n]);
        }   
    }    
}

class Edge{
    public int from;
    public int to;
    public int val;
    public Edge(int from, int to, int val){
        this.from = from;
        this.to = to;
        this.val = val;
    } 
}