【SPFA, DFS】文化之旅

题目

452. 文化之旅 - AcWing题库

试题 算法提高 文化之旅

---

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。

不同的国家可能有相同的文化。

不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 $N，K，M，S，T$ ，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 $1$ 到 $N$ ），文化种数（文化编号为 $1$ 到 $K$ ），道路的条数，以及起点和终点的编号（保证 $S$ 不等于 $T$ ）。

第二行为 $N$ 个整数，每两个整数之间用一个空格隔开，其中第 $i$ 个数 $C_i$ ，表示国家 $i$ 的文化为 $C_i$ 。

接下来的 $K$ 行，每行 $K$ 个整数，每两个整数之间用一个空格隔开，记第 $i$ 行的第 $j$ 个数为 $a_{ij}$ ， $a_{ij} = 1$ 表示文化 $i$ 排斥外来文化 $j$ （ $i$ 等于 $j$ 时表示排斥相同文化的外来人）， $a_{ij} = 0$ 表示不排斥（注意 $i$ 排斥 $j$ 并不保证 $j$ 一定也排斥 $i$ ）。

接下来的 $M$ 行，每行三个整数 $u，v，d$ ，每两个整数之间用一个空格隔开，表示国家 $u$ 与国家 $v$ 有一条距离为 $d$ 的可双向通行的道路（保证 $u$ 不等于 $v$ ，两个国家之间可能有多条道路）。

输出格式

输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出 $-1$ ）。

数据范围

$2 \le N \le 100$ ,
$1 \le K \le 100$ ,
$1 \le M \le N^2$ ,
$1 \le C_i \le K$ ,
$1 \le u,v \le N$ ,
$1 \le d \le 1000$ ,
$1 \le S,T \le N, S \neq T$

输入样例1：

2 2 1 1 2
1 2
0 1
1 0
1 2 10

输出样例1：

-1

输入输出样例1说明：

由于到国家 $2$ 必须要经过国家 $1$ ，而国家 $2$ 的文明却排斥国家 $1$ 的文明，所以不可能到达国家 $2$ 。

输入样例2：

2 2 1 1 2
1 2
0 1
0 0
1 2 10

输出样例2：

10

输入输出样例2说明：

路线为 $1 \to 2$ 。

数据规模和约定：

• 对于 $20\%$ 的数据，有 $2≤N≤8，K≤5$ ；
• 对于 $30\%$ 的数据，有 $2≤N≤10，K≤5$ ；
• 对于 $50\%$ 的数据，有 $2≤N≤20，K≤8$ ；
• 对于 $70\%$ 的数据，有 $2≤N≤100，K≤10$ ；
• 对于 $100\%$ 的数据，有 $2≤N≤100, 1≤K≤100, 1≤M≤ N^2, 1≤k_i≤K, 1≤u, v≤N, 1≤d≤1000, S≠T, 1≤S, T≤N$ 。

解题

方法一：SPFA算法 DFS 剪枝 回溯

思路

显然，没有文化约束的最短路距离一定不大于在文化约束下的最短路距离，我们可以利用这个性质，先以源点 $s$ 为起点，跑一遍 SPFA 算法，预处理出源点 $s$ 到所有点的最短距离（也是所有点到点 $s$ 的最短距离）。然后加上文化约束，对 $t \to s$ 做 DFS （ $s \to t$ 正向求会在某些测试用例上 TLE ），过程中可以根据上面的性质利用预处理得到的最短距离数组做最优性剪枝。

$dfs(u, d)$ （ $u$ 表示当前走到的节点， $d$ 表示从 $t$ 出发已经走过的距离 ）：

• 出口：当走到 $s$ 时（ $u = s$ ），尝试更新答案的最短距离 $ans = \min(ans, d)$ ；
• 枚举与点 $u$ 相连的顶点 $v$ 尝试走：
  • 如果发现 $v$ 的文化已经学到过了，就不能走 $v$ 了（如果他学习了某种文化，则他就不能到达其他有这种文化的国家），跳过；
  • 如果发现 $v$ 的文化与已经学过的文化有冲突（代码实现见 check() 方法），也不能走 $v$ 了（如果他学习了某种文化，则他不能到达排斥这种文化的其他国家），跳过；
  • 否则尝试走 $v$ （ learnt[cul[v]] = true ），并递归下一个点： $dfs(v, d + w[i])$ （ $w[i]$ 为 $u \to v$ 的距离）
    • 回溯（ learnt[cul[v]] = false ）。

剪枝：

• 最优性剪枝1：如果走到中途节点时距离已经大于等于最优解了（ $d \ge ans$ ），就应该直接剪枝。
• 最优性剪枝2：如果走到点 $u$ 时的距离加上「点 $u$ 到 $s$ 不加文化约束的最短距离」已经大于等于最优解了（ $d + dists[u] \ge ans$ ），也应该直接剪枝。

代码

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

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, k, m, s, t;
    static int[] cul;
    static boolean[][] rej;
    static int[] h, e, w, ne;
    static int idx;
    static int[] dists;
    static boolean[] learnt;
    static int ans = INF;

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

    static void spfa(int src) {
        dists = new int[n + 1];
        Arrays.fill(dists, INF);
        dists[src] = 0;
        Queue<Integer> que = new LinkedList<>();
        boolean[] has = new boolean[n + 1];
        que.offer(src);
        has[src] = true;
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (dists[u] + w[i] < dists[v]) {
                    dists[v] = dists[u] + w[i];
                    if (!has[v]) {
                        que.offer(v);
                        has[v] = true;
                    }
                }
            }
        }
    }

    static boolean check(int u) {
        for (int c = 1; c <= k; ++c) {
            if (learnt[c] && rej[c][cul[u]]) return false;
        }
        return true;
    }

    static void dfs(int u, int d) {
        if (d >= ans) return;
        if (d + dists[u] >= ans) return;
        if (u == s) {
            ans = d;
            return;
        }
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!learnt[cul[v]] && check(v)) {
                learnt[cul[v]] = true;
                dfs(v, d + w[i]);
                learnt[cul[v]] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); k = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        in.nextToken(); s = (int) in.nval;
        in.nextToken(); t = (int) in.nval;
        cul = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken(); cul[i] = (int) in.nval;
        }
        rej = new boolean[k + 1][k + 1];
        for (int i = 1; i <= k; ++i) {
            for (int j = 1; j <= k; ++j) {
                in.nextToken(); rej[i][j] = (in.nval == 1 ? true : false);
            }
        }
        h = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[m * 2];
        ne = new int[m * 2];
        w = new int[m * 2];
        while (m-- > 0) {
            in.nextToken(); int u = (int) in.nval;
            in.nextToken(); int v = (int) in.nval;
            in.nextToken(); int w = (int) in.nval;
            add(u, v, w); add(v, u, w);
        }
        spfa(s);
        if (dists[t] == INF) {
            System.out.println(-1);
            return;
        }
        learnt = new boolean[k + 1];
        learnt[cul[t]] = true;
        dfs(t, 0);
        System.out.println(ans > INF / 2 ? -1 : ans);
    }
}