DAY60Bellman_ford 算法

队列优化算法

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。
如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 “unconnected”。

import java.util.*;

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



    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int m=in.nextInt();
            List<List<Edge>> graph=new ArrayList<>();

            for(int i=0;i<n;i++){
                graph.add(new ArrayList<>());
            }
            for(int i=0;i<m;i++){
                int from=in.nextInt();
                int to=in.nextInt();
                int val=in.nextInt();
                graph.get(from).add(new Edge(from, to, val));

            }
            int[]minDist=new int[n+1];
            Arrays.fill(minDist,Integer.MAX_VALUE);
            minDist[1]=0;

            Queue<Integer> queue=new LinkedList<>();
            queue.offer(1);
            boolean[] isInQueue=new boolean[n+1];

            while(!queue.isEmpty()){
                int curNode=queue.poll();
                isInQueue[curNode]=false;
                for(Edge edge:graph.get(curNode)){
                    if(minDist[edge.to]>minDist[edge.from]+edge.val){
                        minDist[edge.to]=minDist[edge.from]+edge.val;
                        if(!isInQueue[edge.to]){
                            queue.offer(edge.to);
                            isInQueue[edge.to]=true;
                        }
                    }
                }
            }
            if(minDist[n]==Integer.MAX_VALUE){
                System.out.println("unconnected");
            }else{
                System.out.println(minDist[n]);
            }
        }
     
    }

判断负权回路

负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

import java.util.*;

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



    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int m=in.nextInt();
            List<List<Edge>> graph=new ArrayList<>();

            for(int i=0;i<n;i++){
                graph.add(new ArrayList<>());
            }
            for(int i=0;i<m;i++){
                int from=in.nextInt();
                int to=in.nextInt();
                int val=in.nextInt();
                graph.get(from).add(new Edge(from, to, val));

            }
            int[]minDist=new int[n+1];
            Arrays.fill(minDist,Integer.MAX_VALUE);
            minDist[1]=0;

            Queue<Integer> queue=new LinkedList<>();
            queue.offer(1);
            boolean[] isInQueue=new boolean[n+1];

            int[] count=new int[n+1];
            count[1]++;

            boolean flag=false;

            while(!queue.isEmpty()){
                int curNode=queue.poll();
                isInQueue[curNode]=false;
                for(Edge edge:graph.get(curNode)){
                    if(minDist[edge.to]>minDist[edge.from]+edge.val){
                        minDist[edge.to]=minDist[edge.from]+edge.val;
                        if(!isInQueue[edge.to]){
                            queue.offer(edge.to);
                            count[edge.to]++;
                            isInQueue[edge.to]=true;
                        }

                        if(count[edge.to]==n){
                            flag=true;
                            while (!queue.isEmpty()) {
                                queue.poll();
                                
                            }
                            break;
                        }

                    }
                }
            }
            if(flag){
                System.out.println("circle");
            }else if(minDist[n]==Integer.MAX_VALUE){
                System.out.println("unconnected");
            }else{
                System.out.println(minDist[n]);
            }
        }
     
    }

加了一个count数组，若松弛 n 次以上，则存在负权回路

单源有限最短路

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。

权值为正表示扣除了政府补贴后运输货物仍需支付的费用；

权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本

import java.util.*;

public class Main {
    // 基于Bellman_for一般解法解决单源最短路径问题
    // Define an inner class Edge
    static class Edge {
        int from;
        int to;
        int val;
        public Edge(int from, int to, int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // Input processing
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Edge> graph = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int val = sc.nextInt();
            graph.add(new Edge(from, to, val));
        }

        int src = sc.nextInt();
        int dst = sc.nextInt();
        int k = sc.nextInt();

        int[] minDist = new int[n + 1];
        int[] minDistCopy;

        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[src] = 0;

        for (int i = 0; i < k + 1; i++) { // Relax all edges k + 1 times
            minDistCopy = Arrays.copyOf(minDist, n + 1);
            for (Edge edge : graph) {
                int from = edge.from;
                int to = edge.to;
                int val = edge.val;
                // Use minDistCopy to calculate minDist
                if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) {
                    minDist[to] = minDistCopy[from] + val;
                }
            }
        }
        
        // Output printing
        if (minDist[dst] == Integer.MAX_VALUE) {
            System.out.println("unreachable");
        } else {
            System.out.println(minDist[dst]);
        }
    }
}