[ARC061E]Snuke's Subway Trip 题解

题目链接：[ARC061E]Snuke's Subway Trip

题意：

Snuke的城镇有地铁行驶，地铁线路图包括 \(N\) 个站点和 \(M\) 个地铁线。站点被从 \(1\) 到 \(N\) 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。

第 \(i\) 条线路( \(1≤i≤M\) )是直接连接 \(p_i\) 与 \(q_i\) 的双向铁路，中间不存在其他站点，且这条铁路由 \(c_i\) 公司所拥有。

如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。

Snuke在 \(1\) 号站的位置出发，他想通过地铁去第 \(N\) 站，请求出最小钱数。如果无法到达第 \(N\) 站，输出 \(-1\)。

输入格式：

第一行，输入 \(N,M\)

接下来的 \(M\) 行，输入 \(p_i\) \(q_i\) \(c_i\) ，代表 \(p_i\) 与 \(q_i\) 中间有直接连接的双向边，且这条铁路由 \(c_i\) 公司所拥有。

输出格式：

输出最小钱数（若无法到达，输出 \(-1\) ）

数据范围：

\(2\le N \le 10^5,~0\le M\le 2×10^5,~1\le p_i,q_i\le N,~1\ \leq\ c_i\ \leq\ 10^6,~p_i \ne q_i\)

容易发现，由相同颜色边连接的一个联通块，是可以在其中自由穿行而没有花费的

如果我们把这样的联通块合并成一个点，那么原题就可以用 01bfs 解决了。

怎么合并这些块呢？我们可以建一个虚点 \(u_0\) ，让联通块里的所有点 \(v\) 连边 \((u_0,v,1)\) 和 \((v,u,0)\)

具体方法就是枚举所有颜色的边，把这些边涉及的点拿出来，再用并查集合并找联通块数量，最后连边。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

const int C = 1e6; 

int n,m,tot,fa[N],col[N],d[N * 2];
vector<pii> e[C + 15], g[N * 2];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void addEdge(int u,int v) {
    g[u].emplace_back(v, 0); g[v].emplace_back(u, 1);
}
void solve()
{
    deque<int> q; q.push_back(1);
    memset(d, -1, sizeof(d)); d[1] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop_front();
        for(auto [v, w] : g[u]) if(d[v] == -1)
        {
            d[v] = d[u] + w;
            if(w == 1) q.push_back(v); else q.push_front(v);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; tot = n;
    for(int i = 1,u,v,c; i <= m; i++)
    {
        cin >> u >> v >> c;
        e[c].emplace_back(u, v);
    }
    for(int i = 1; i <= C; i++) if(!e[i].empty())
    {
        vector<int> p;
        for(auto [x, y] : e[i]) { p.emplace_back(x); p.emplace_back(y); }
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        for(int x : p) fa[x] = x;
        for(auto [x, y] : e[i]) fa[find(x)] = find(y);
        for(int x : p) if(find(x) == x) col[x] = ++tot;
        for(int x : p) addEdge(x, col[find(x)]);
    }
    solve(); cout << d[n] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/_post/636442