前提・実現したいこと
ABC218のF問題を解いています。添付の回答で1ケースのみWAしてしまいます。
WAするケースが自力では発見できず質問させていただきました。
分かる方がおられましたらご教授いただければ幸いです。
https://atcoder.jp/contests/abc218/tasks/abc218_f
発生している問題・エラーメッセージ
case17のみWA
該当のソースコード
C++
1#include <bits/stdc++.h> 2#include <atcoder/all> 3 4using ll = long long; 5const ll INF = 100100100; 6struct Edge 7{ 8 ll from; 9 ll to; 10 ll id; 11 Edge() {} 12 Edge(ll _from, ll _to, ll _id) { 13 from = _from; 14 to = _to; 15 id = _id; 16 } 17}; 18 19std::vector<std::vector<Edge>> G; 20 21int main() 22{ 23 ll N, M; 24 std::cin >> N >> M; 25 26 G.resize(N); 27 28 for (ll i = 0; i < M; i++) { 29 ll s, t; 30 std::cin >> s >> t; 31 s--; t--; 32 G[s].emplace_back(Edge(s, t, i)); 33 } 34 35 std::queue<ll> que; 36 std::vector<ll> dist(N, INF); 37 std::vector<Edge> path(N); 38 que.emplace(0); 39 dist[0] = 0; 40 41 while (que.size() > 0) { 42 ll node = que.front(); 43 que.pop(); 44 45 for (auto& itr : G[node]) { 46 if (dist[itr.to] == INF) { 47 que.emplace(itr.to); 48 dist[itr.to] = dist[node] + 1; 49 path[itr.to] = itr; 50 } 51 } 52 } 53 54 if (dist[N - 1] == INF) { 55 std::cout << -1 << std::endl; 56 return 0; 57 } 58 59 ll curNode = N - 1; 60 std::vector<ll> shortestPath; 61 while (curNode > 0) { 62 shortestPath.emplace_back(path[curNode].id); 63 curNode = path[curNode].from; 64 } 65 66 std::vector<ll> ans(M, dist[N - 1]); 67 68 for (auto& banEdge : shortestPath) { 69 std::vector<ll> distNew(N, INF); 70 que.emplace(0); 71 distNew[0] = 0; 72 73 while (que.size() > 0) { 74 ll node = que.front(); 75 que.pop(); 76 77 for (auto& itr : G[node]) { 78 if (itr.id == banEdge) { 79 continue; 80 } 81 82 if (distNew[itr.to] == INF) { 83 que.emplace(itr.to); 84 distNew[itr.to] = distNew[node] + 1; 85 path[itr.to] = itr; 86 } 87 } 88 } 89 if (distNew[N - 1] == INF) { 90 distNew[N - 1] = -1; 91 } 92 ans[banEdge] = distNew[N - 1]; 93 } 94 95 for (auto& curAns : ans) { 96 std::cout << curAns << std::endl; 97 } 98 99 return 0; 100}
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/09/12 08:27