ICPC2024昆明邀请赛 J The Quest for El Dorado 题解

Question

The Quest for El Dorado

有一个王国，有 \(n\) 个城市和 \(m\) 条双向铁路连接这些城市。第 \(i\) 条铁路由第 \(c_i\) 家铁路公司运营，铁路的长度为\(l_i\)。

你想要环游这个国家，从城市 \(1\) 出发。为了你的旅行，你购买了 \(k\) 张火车票。第 \(i\) 张火车票用两个整数 \(a_i\) 和\(b_i\) 表示，意味着如果你使用这张票，你可以一次性通过一些铁路旅行，只要它们都是由第 \(a_i\) 家公司运营的，并且它们的总长度不超过 \(b_i\) 。当使用一张票时，也允许只停留在当前城市。你只能一次使用一张票，并且每张票只能使用一次。

由于你觉得确定使用火车票的顺序很麻烦，所以你决定按照它们当前的顺序使用。更正式地说，你要执行 \(k\) 次操作。在第\(i\) 次操作中，你可以选择留在当前城市 \(u\) ；或者选择另一个城市 \(v\)，使得从城市 \(u\) 到城市 \(v\) 存在一条路径，该路径上的所有铁路都由第 \(a_i\) 家公司运营，且铁路的总长度不超过 \(b_i\)，最终移到城市 \(v\)。

对于每个城市，确定在使用了所有 \(k\) 张火车票之后是否可能到达该城市。

Solution

类似于 dij 的思想，开 \(m\) 个优先队列，把边按照公司分类，当处理到 \(C\) 公司时，只需要把 \(C\) 的那个优先队列拿出来刷一次类似于 \(dij\) 的算法，把这一次加入的点放入一个集合 \(vis\) 中，在处理完 \(C\) 之后更新 \(dis\) ，把 \(vis\) 中的 \(dis\) 都改成 \(0\)

具体实现时，几下这条边是在第几张车票时加入的，如果不是在这张车票加入的话就 continue 掉

这道题需要你非常理解 dij 的思想，把 dij 的过程分阶段进行

Code

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

typedef pair<int, int> pii;
typedef tuple<int, int, int> t3;

const int INF = -1;
struct Edge {
    int from, to, c, l, idx;
    Edge(int from, int to, int c, int l, int idx) : from(from), to(to), c(c), l(l), idx(idx) {}
};

void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<Edge> edges; int cnt = 0;
    vector<vector<int>> g(n + 1);
    vector<int> dis(n + 1, INF);
    for (int i = 0; i < m; i++) {
        int u, v, c, l; cin >> u >> v >> c >> l;
        edges.push_back(Edge(u, v, c, l, cnt++));
        g[u].push_back(cnt - 1);
        edges.push_back(Edge(v, u, c, l, cnt++));
        g[v].push_back(cnt - 1);
    }
    typedef priority_queue<t3, vector<t3>, greater<t3>> pq;
    vector<pq> p(m + 1);
    map<int, int> mp; mp[1] = 1;
    for (auto i : g[1]) {
        Edge &e = edges[i];
        p[e.c].push({e.l, e.to, 1});
    }
    for(int i = 1; i <= k; i++) {
        int C, L; cin >> C >> L;
        while (!p[C].empty()) {
            auto [d, u, idx] = p[C].top();
            if (d > L) break;
            p[C].pop();
            if (idx != 0 && idx != i) continue;
            if (dis[u] == 0 || mp.count(u)) continue;
            mp[u] = 1;
            for (auto j : g[u]) {
                Edge &e = edges[j];
                if (d + e.l > L) continue;
                if (e.c == C) p[e.c].push({d + e.l, e.to, i});
            }
        }
        for (auto [u, _] : mp) {
            dis[u] = 0;
            for (auto j : g[u]) {
                Edge &e = edges[j];
                p[e.c].push({e.l, e.to, 0});
            }
        }
        mp.clear();
    }
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0) cout << "1";
        else cout << "0";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}