$$\color{Red}{道路与航线(拓扑图+Dijkstra)——【详细代码解析注释】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

解析

这道题利用了拓扑排序 -> 我的拓扑排序题解

同时这道题不能使用SPFA 只能使用Dijkstra【有负权边】

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

解析

首先这道题，并非完全不能用SPFA，其实可以经过优化连通块的距离计算方法，把SPFA的负权限制抹去【因为这道题负权边的限制只是在连通块之间，而且是有向边】。

但是还是不推荐，因为这道题的数据量很大，spfa的效果由题目的数据来定，数据量大，或者是出题人故意出卡spfa的数据的情况下，无法ac。

故这道题还是采用 堆优化 dijkstra 加 拓扑图性质

图结构分析

首先我们根据题意，其实需要先构思清楚到底整个图的结构是怎么样的，我们可以看到，道路都是无向边，故道路里面的点肯定彼此可达的，是联通图。

而航线是单向边且可以有负权边，这道题有一个很重要的性质-> 一旦满足 A 可达 B ：A -> B，一定不存在任何通路使得 B 可达 A ： B -> A

综合可得——》 有道路的连通块一定彼此可达，且一旦这个连通块中的点 A 向别的点 B 联通一条航线，那么A和B势必不在一个连通块【即没有道路可达】。联向的点 B 所在的连通块【单点也可以看作一个连通块】势必连通块的点没有任何一个点产生一条到 A所在的连通块的航线【即没有 B的连通块到 A的连通块的航线】。

故立马可抽象出，各个连通块抽象成一个点，且这些抽象出来的点构成拓扑图。且每个连通块内部的点，没有负权边，可以使用Dijkstra，而连通块之间可以使用 bfs【拓扑排序】。

做法

上面的图结构分析已经抽象出做法了，具体而言，我们给在一个连通块的点标号【具体做法，未读入航线之前先进行dfs，类似染色法】，然后再进行连通块的拓扑排序，此时，我们对单独的连通块进行dijkstra，同时更新每个连通块的入度。一旦入度为0就放入拓扑排序的队列。具体的做法见代码和注释。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;


/**
 * @author Fanxy
 */
public class Main {

    private static final int INF = 0x3f3f3f3f;
    static int n, roadCount, routCount, start, blockCount, idx;
    static int N = 25010, M = 150010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] r = new int[N];
    static int[] d = new int[N];
    static boolean[] st = new boolean[N];
    static LinkedList<Integer> q = new LinkedList<>();
    // 拓扑排序的队列
    static int[] blockId = new int[N];
    // 对应每个连通块的点集合
    static ArrayList<Integer>[] blocks = new ArrayList[N];

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

    // 给相同的连通块标号 并放入对应的集合中
    static void dfs(int root, int bId) {
        blockId[root] = bId;
        if (blocks[bId] == null) blocks[bId] = new ArrayList<>();
        blocks[bId].add(root);
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];
            if (blockId[j] == 0) dfs(j, bId);
        }
    }

    // 拓扑排序
    static void topSort() {
        // 给所有的点到起点的距离初始化无穷
        Arrays.fill(d, INF);
        d[start] = 0;
        for (int i = 1; i <= blockCount; i++) {
            if (r[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int bId = q.removeFirst();
            dijkstra(bId);
        }
    }

    static void dijkstra(int bId) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        for (Integer node : blocks[bId]) heap.add(new int[]{d[node], node});
        while (!heap.isEmpty()) {
            int[] top = heap.remove();
            int num = top[1];
            int dist = top[0];
            if (st[num]) continue;
            st[num] = true;
            for (int i = h[num]; i != -1; i = ne[i]) {
                int j = e[i];
                // 不在一个联通块 则减小入度 如果入度为0 这个的连通块进入topSort的队列 等待这个连通块的dijkstra
                if (blockId[j] != blockId[num] && --r[blockId[j]] == 0) q.add(blockId[j]);
                // 无论是否在一个连通块 都要更新距离 而如果在一个连通块 进入 dijkstra的优先队列
                if (d[j] > dist + w[i]) {
                    d[j] = dist + w[i];
                    if (blockId[j] == blockId[num]) heap.add(new int[]{d[j], j});
                }
            }
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        roadCount = Integer.parseInt(s1[1]);
        routCount = Integer.parseInt(s1[2]);
        start = Integer.parseInt(s1[3]);
        // 加边前给邻接表初始化链表尾部
        Arrays.fill(h, -1);
        // 道路连边 此时形成多个互不连通的联通块
        for (int i = 0; i < roadCount; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }
        // 给所有的连通块标号
        for (int i = 1; i <= n; i++) {
            if (blockId[i] == 0) {
                blockCount++;
                dfs(i, blockCount);
            }
        }
        // 给所有的航线连单向边 而对应的连通块整体的入度加一
        for (int i = 0; i < routCount; i++) {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            int c = Integer.parseInt(s3[2]);
            add(a, b, c);
            r[blockId[b]]++;
        }
        // 进行联通块的拓扑排序 拓扑排序中进行Dijkstra
        topSort();
        // 答案输出 因为有负边 故不能用INF 应该用大数
        for (int i = 1; i <= n; i++) {
            if (d[i] > INF / 2) System.out.println("NO PATH");
            else System.out.println(d[i]);
        }
    }
}