AtCoder Regular Contest 052 C: 高橋くんと不思議な道
解法
(辺Bを通った数, 頂点vまでのコスト) を頂点としてダイクストラする。
コード
#include <bits/stdc++.h> using namespace std; typedef tuple<int, int, int> P; // cost, count, vertex int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<vector<int>> aGraph(N), bGraph(N); for (int i = 0; i < M; ++i) { int c, a, b; cin >> c >> a >> b; if (c == 0) { aGraph[a].push_back(b); aGraph[b].push_back(a); } else { bGraph[a].push_back(b); bGraph[b].push_back(a); } } vector<map<int, int>> dist(N); dist[0][0] = 0; priority_queue<P, vector<P>, greater<P>> Q; vector<int> ans(N, 1e8); ans[0] = 0; Q.emplace(0, 0, 0); while (!Q.empty()) { int cost, cnt, v; tie(cost, cnt, v) = Q.top(); Q.pop(); for (const auto &next : aGraph[v]) { for (const auto &p : dist[next]) if (p.first <= cnt && p.second <= cost + 1) goto prune_a; dist[next][cnt] = cost + 1; Q.emplace(cost + 1, cnt, next); if (ans[next] > cost + 1) ans[next] = cost + 1; prune_a:; } for (const auto &next : bGraph[v]) { for (const auto &p : dist[next]) if (p.first <= cnt + 1 && p.second <= cost + cnt + 1) goto prune_b; dist[next][cnt + 1] = cost + cnt + 1; Q.emplace(cost + cnt + 1, cnt + 1, next); if (ans[next] > cost + cnt + 1) ans[next] = cost + cnt + 1; prune_b:; } } for (const auto &d : ans) cout << d << "\n"; }