AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題

arc061.contest.atcoder.jp

解法

koyumeishi さんに教えてもらいました。

@mayoko_ こんな感じでわかるかなぁ…？ 赤がコスト 1 、 黒がコスト 0 の辺で、最後に2で割るようにしました。 人のを見ると中継点に入る辺(出る辺)のみコスト1にする派もいるっぽいです pic.twitter.com/4COTPu4rvY

— koyumeishi (@koyumeishi_) 2016年9月11日

各頂点に新しくノードを追加します(電車を乗り換えるときに必ず通る改札みたいなイメージ)。

おなじ路線を使っている間はコスト 0 ですが, 別の路線を使おうと思ったときはこの改札をコスト 1 で通らなければならない, というようにすると辺の数は O(M), 頂点の数は O(N+M) で抑えられるので, ダイクストラすることで問題を解くことができます。

const int MAXM = 202020;
vector<pii> G[3*MAXM];
map<pii, int> sid;
int lastId = 0;
int P[MAXM], Q[MAXM], C[MAXM];

int getid(int v, int c) {
    pii p(v, c);
    if (sid.find(p) != sid.end()) return sid[p];
    return sid[p] = lastId++;
}

void addEdge(int p, int q, int c) {
    int v = getid(p, c), u = getid(q, c);
    G[v].emplace_back(u, 0);
    G[u].emplace_back(v, 0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i] >> C[i];
        P[i]--; Q[i]--;
        addEdge(P[i], Q[i], C[i]);
    }
    for (int i = 0; i < M; i++) {
        G[getid(P[i], C[i])].emplace_back(lastId+P[i], 1);
        G[getid(Q[i], C[i])].emplace_back(lastId+Q[i], 1);
        G[lastId + P[i]].emplace_back(getid(P[i], C[i]), 1);
        G[lastId + Q[i]].emplace_back(getid(Q[i], C[i]), 1);
    }
    const int INF = 1e9;
    vector<int> d(lastId+N, INF); d[lastId] = 0;
    priority_queue<pii> que;
    que.push(pii(0, lastId));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second, dist = -p.first;
        if (dist > d[u]) continue;
        for (auto e : G[u]) {
            int v = e.first, c = e.second;
            if (d[v] > d[u]+c) {
                d[v] = d[u]+c;
                que.push(pii(-d[v], v));
            }
        }
    }
    int ans = d[lastId+N-1];
    if (ans == INF) ans = -1;
    else ans /= 2;
    cout << ans << endl;
    return 0;
}