ARC061C

james1BadCreeper · 2023-09-21 10:32:29 · 题解

用同样颜色的边所连接成的连通块可以互相到达，不难想到建一个虚点，将这个联通块内的所有点向虚点连一个权值为 0 的边，由这个连通块切换到别的连通块都需要 1 的代价，因此虚点向连通块内所有点连权值为 1 的边。

并查集加 01 BFS 就可以完成这个过程，应该是 O(m\log m) 的。

#include <bits/stdc++.h> 
using namespace std; 
const int C = 1000000; 

int n, m, tot; 
vector<pair<int, int>> E[1000005]; 
int fa[200005]; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int col[200005]; 
vector<pair<int, int>> G[400005]; 

inline void addedge(int u, int v) {
    G[u].emplace_back(v, 0); 
    G[v].emplace_back(u, 1); 
}

int d[400005]; 
void bfs(void) {
    deque<int> q; memset(d, 0xff, sizeof d); d[1] = 0; q.push_back(1); 
    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); 
        }
    }
    cout << d[n] << "\n"; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; tot = n; 
    while (m--) {
        int u, v, c; cin >> u >> v >> c; 
        E[c].emplace_back(u, v); 
    }
    for (int i = 1; i <= C; ++i) if (E[i].size()) {
        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)]); 
    } bfs(); 
    return 0; 
}