题解：CF1941G Rudolf and Subway

2huk · 2024-03-17 14:08:02 · 题解

给定一张 n 个点 m 条边的图。第 i 条边表示地铁 c_i 号线连接了点 a_i, b_i。

求从 s 点到 t 点最少需要换乘地铁几次。

换乘地铁的次数，也就是登上一辆新地铁的次数。这里的“新”指当前是第一辆地铁或当前地铁不同于上一辆地铁。所以我们只需要计算最小的上车次数即可。

我们不妨把每辆地铁都看成一个点。

如果存在一条边 u_i \to v_i 的边权为 c_i，就代表这里存在一种上 c_i 车的方案。那么我们建一条新边 u_i \to c_i 边权为 1，表示可以从 u_i 点耗费 1 的代价登上 c_i 地铁。

同理，下车的次数我们是不需要考虑的，所以我们建 c_i \to v_i 边权为 0 表示下车不需要消耗代价。

最终求 s \to t 的最短路即可。由于边权均为 0/1，所以可以 0-1 bfs 代替 Dijkstra。

vector<PII> g[N];
int dis[N];
bool st[N];

void Luogu_UID_748509() {
    int n, m; fin >> n >> m;
    int cnt = n;

    for (int i = 1; i <= n + m + 1; ++ i ) g[i].clear();
    map<int, int> col;
    while (m -- ) {
        int u, v, w; fin >> u >> v >> w;
        if (!col.count(w)) col[w] = ++ cnt;
        g[u].push_back({col[w], 1});
        g[v].push_back({col[w], 1});
        g[col[w]].push_back({u, 0});
        g[col[w]].push_back({v, 0});
    }
    int s, t; fin >> s >> t;

    deque<int> q;
    q.push_back(s);
    for (int i = 1; i <= n + cnt + 1; ++ i ) dis[i] = 1e9, st[i] = 0;
    dis[s] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop_front();
        if (st[u]) continue;
        st[u] = true;
        for (auto [v, w] : g[u]) if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            if (w) q.push_back(v);
            else q.push_front(v);
        }
    }
    fout << dis[t] << '\n';
}