AtCoder Regular Contest 052 C: 高橋くんと不思議な道

問題

C: 高橋くんと不思議な道 - AtCoder Regular Contest 052 | AtCoder

解法

(辺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";
}