C++の練習を兼ねて, AtCoder Regular Contest 090 の 問題E (Avoiding Collision) を解いてみた.
■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 090 解説 を ご覧下さい.
■C++版プログラム(問題E/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
// 解き直し. // https://img.atcoder.jp/arc090/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using PII = pair<int, int>; using PLI = pair<LL, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second #define pb push_back const LL INF = 202020202020202020; const LL MOD = 1e9 + 7; LL dp1[202020]; // 頂点 S から 頂点 v への 最短路 の 個数. LL dp2[202020]; // 頂点 v から 頂点 T への 最短路 の 個数. struct edge{ int n; // 次の頂点. LL c; // コスト. bool operator < (const edge &E) const{ return c > E.c; } }; LL d[101010]; // 頂点 S から 各頂点への 最短距離 を 保存. vector<edge> G[101010]; // https://ja.wikipedia.org/wiki/ダイクストラ法 // グラフを最良優先探索する. // ※dijkstraの動作確認用. // @param s: 今回探索する頂点番号. // @return: 特に無し. void dijkstra(int s){ // 1. 初期化. priority_queue<edge> pq; // 2. 始点設定. d[s] = 0; pq.push({s, 0LL}); // 3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 4. 探索を継続するために, 頂点を取得. edge e = pq.top(); pq.pop(); int cn = e.n; LL cc = e.c; // 5. より小さい距離が設定済みなら, Skip. if(d[cn] < cc) continue; // 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新. for(auto &g : G[cn]){ int nn = g.n; LL nc = cc + g.c; // 最短経路更新. if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc}); } } } int main(){ // 1. 入力情報. int N, M, S, T; scanf("%d %d %d %d", &N, &M, &S, &T); S--, T--; map<PII, LL> m; rep(i, M){ int u, v; LL d; scanf("%d %d %lld", &u, &v, &d); u--, v--; G[u].pb({v, d}); G[v].pb({u, d}); m[{u, v}] = d; m[{v, u}] = d; } // 2. 頂点 S から 各頂点への最短経路を求める(ダイクストラ法). rep(i, N) d[i] = INF; dijkstra(S); // rep(i, N) printf("%lld ", d[i]); // puts(""); // 3. 頂点 S から 遠い順, 近い順 に並び替え. priority_queue<PLI> fPq; priority_queue<PLI, vector<PLI>, greater<PLI>> nPq; rep(i, N){ // {距離, 頂点番号} fPq.push({d[i], i}); nPq.push({d[i], i}); } // 4. dp1更新. // -> 頂点 S から 頂点 v への 最短路 の 個数 を 計算. dp1[S] = 1; while(!nPq.empty()){ // 4-1. 頂点 u を一つ取り出す. PLI p = nPq.top(); nPq.pop(); // 4-2. 頂点 u の 頂点番号は? int u = p.b; // 4-3. 頂点 u から 頂点 v に向かって, dp1更新. for(auto &e : G[u]){ // d[u] + c = d[v] が 成立するか? int v = e.n; LL cUV = m[{u, v}]; if(d[u] + cUV == d[v]) dp1[v] += dp1[u], dp1[v] %= MOD; } } // rep(i, N) printf("%lld ", dp1[i]); // puts(""); // 5. dp2更新. // -> 頂点 v から 頂点 T への 最短路 の 個数 を 計算. dp2[T] = 1; while(!fPq.empty()){ // 4-1. 頂点 u を一つ取り出す. PLI p = fPq.top(); fPq.pop(); // 4-2. 頂点 u の 頂点番号は? int u = p.b; // 4-3. 頂点 u から 頂点 v に向かって, dp2更新. for(auto &e : G[u]){ // d[v] + c = d[u] が 成立するか? int v = e.n; LL cUV = m[{u, v}]; if(d[v] + cUV == d[u]) dp2[v] += dp2[u], dp2[v] %= MOD; } } // rep(i, N) printf("%lld ", dp2[i]); // puts(""); // 6. 最短路の組の個数は? // 6-1. 途中で出会うものも含めた最短路の選び方の組. LL p1 = dp1[T] * dp1[T] % MOD; // 6-2. 途中(頂点上)で出会う最短路の選び方の組. LL p2 = 0; rep(i, N){ // 2 * d[v] = d[T] となる 各頂点 v で集計. if(2 * d[i] == d[T]){ LL s1 = dp1[i] * dp1[i] % MOD; LL s2 = dp2[i] * dp2[i] % MOD; p2 += s1 * s2 % MOD; p2 %= MOD; } } // 6-3. 途中(辺上)で出会う最短路の選び方の組. LL p3 = 0; for(auto &e : m){ int u = e.a.a, v = e.a.b; LL c = e.b; // 2 * d[u] < d[T] かつ 2 * d[v] > d[T] かつ d[u] + c = d[v] となる 各辺(u, v) で集計. if(2 * d[u] < d[T] && 2 * d[v] > d[T] && d[u] + c == d[v]){ LL s1 = dp1[u] * dp1[u] % MOD; LL s2 = dp2[v] * dp2[v] % MOD; p3 += s1 * s2 % MOD; p3 %= MOD; } } // 7. 出力. LL ans = (p1 + (MOD - p2) + (MOD - p3)) % MOD; printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
[入力例] 4 4 1 3 1 2 1 2 3 1 3 4 1 4 1 1 [出力例] 2 ※AtCoderテストケースより [入力例] 3 3 1 3 1 2 1 2 3 1 3 1 2 [出力例] 2 ※AtCoderテストケースより [入力例] 8 13 4 2 7 3 9 6 2 3 1 6 4 7 6 9 3 8 9 1 2 2 2 8 12 8 6 9 2 5 5 4 2 18 5 3 7 5 1 515371567 4 8 6 [出力例] 6 ※AtCoderテストケースより [入力例] 10 12 5 10 1 3 1 1 2 2 2 6 3 6 5 2 3 5 8 3 10 10 3 4 4 4 10 6 10 7 12 8 7 7 9 8 2 10 9 3 [出力例] 8 |
■参照サイト
AtCoder Regular Contest 090