题解：P1811 最短路

· · 题解

P1811 最短路

水一篇题解。

题目分析

这道题看是一个简单的无向图最短路问题添加了一点限制条件，即给定 K 个三元组 (A, B, C)，意思是如果你刚刚从 A 走到 B，那么不允许继续从 B 走到 C，但是如果你从 B 走到 A，则是没有限制的。

这说明着路径是否合法不仅和当前点有关，还和上一个点有关。针对简单的边权为 1 的最短路问题，很容易想到使用 dist[u] 记录最短路，而针对这题，需要把状态扩展为 dist[u][prev]，表示从 prev 到 u 的最短距离。

思路实现

  1. 状态扩展
    相较于普通的边权为 1 的最短路算法，将普通的每个点的状态记录增加了对之前点的记录，相当于记录了 prev 到 u 的有向边的状态。

  2. 多个 C 的存储
    对于每个 (A,B)，可能会有多个禁止的 C。 因此使用 id_map[A][B] 给每个二元组分配一个编号，对应到 ban_list 中的集合，存储所有禁止的 C。
    如此一来，就能实现 \mathcal{O}(1) 地查询限制。

  3. BFS的状态转移
    从 u 可以尝试走到 v。
    如果存在 (prev, u, v)，就跳过。
    否则更新 dist[v][u] = dist[u][prev] + 1，并记录前驱，用于还原路径。

  4. 路径还原
    当BFS找到终点 N 时，输出 dist[N][prev]。
    然后沿着 fa[N][N] 数组回溯路径，最后逆序输出。

代码实现

下面的代码使用了二维数组 dist[N][N] 和 fa[N][N] 来存状态，使用 id_map 和 ban_list 存储限制条件。 复杂度为 \mathcal{O}(n^2+m+k)，在题目数据范围内可以通过。

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

int dist[N][N];                 // dist[u][prev]
pair<int, int> fa[N][N];        // 记录前驱
vector<int> graph[N];              // 邻接表
int id_map[N][N];               // (a,b) -> 下标
vector<unordered_set<int>> ban_list;  // 对应的禁止集合

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 建图
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // 初始化 id_map
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            id_map[i][j] = -1;

    // 读入限制条件
    for (int i = 0; i < k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (id_map[a][b] == -1) {
            id_map[a][b] = ban_list.size();
            ban_list.push_back(unordered_set<int>());
        }
        ban_list[id_map[a][b]].insert(c);
    }

    // 初始化 dist
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = -1;

    // BFS
    queue<pair<int, int>> q;
    dist[1][0] = 0;
    fa[1][0] = {0, 0};
    q.push({1, 0});

    while (!q.empty()) {
        int u = q.front().first;
        int prev = q.front().second;
        q.pop();

        // 到达终点
        if (u == n) {
            cout << dist[u][prev] << endl;

            // 路径回溯
            vector<int> path;
            int cur_u = u, cur_prev = prev;
            path.push_back(cur_u);
            while (cur_u != 1) {
                auto p = fa[cur_u][cur_prev];
                cur_u = p.first;
                cur_prev = p.second;
                path.push_back(cur_u);
            }
            reverse(path.begin(), path.end());
            for (size_t i = 0; i < path.size(); i++) {
                cout << path[i] << (i + 1 == path.size() ? '\n' : ' ');
            }
            return 0;
        }

        // 扩展邻居
        for (int v : graph[u]) {
            int id = id_map[prev][u];
            if (id != -1 && ban_list[id].count(v)) {
                continue; // 被禁止
            }

            if (dist[v][u] == -1) {
                dist[v][u] = dist[u][prev] + 1;
                fa[v][u] = {u, prev};
                q.push({v, u});
            }
        }
    }

    // 无解
    cout << -1 << "\n";
    return 0;
}

完结撒花。