C++の練習を兼ねて, AtCoder Beginner Contest 271 の 問題E (Subsequence Path) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できた.
2. 実装に苦労したものの, 問題Eで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. dp更新式は, 解説プログラムを見ると, 非常にシンプルに実装されていたので, 実装のシンプル化は, 引き続き, 今後の課題にしたいと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 271 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc271/editorial/4924 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using T3 = tuple<int, int, LL>; using vt = vector<T3>; #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 pb push_back const LL INF = 101010101010101010; int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); vt t; set<int> Idx[N]; rep(i, M){ int a, b; LL c; scanf("%d %d %lld", &a, &b, &c); --a; --b; // 辺(a, b) の 情報. t.emplace_back(a, b, c); // 辺(a, b) を, 頂点 a を 基準 に 保存. Idx[a].insert(b); } vi E(K); rep(i, K){ scanf("%d", &E[i]); --E[i]; } // 2. dp更新. LL dp[N]; rep(i, N) dp[i] = INF; dp[0] = 0; rep(i, K){ // 辺情報(番号: E[i]). int ca = get<0>(t[E[i]]); int cb = get<1>(t[E[i]]); LL cc = get<2>(t[E[i]]); // 最小値更新. dp[cb] = min(dp[cb], dp[ca] + cc); // ループ(i) の 範囲は, [0, K - 1] に ロジック修正. // -> テストケース(test_01.txt)で, WA だったことに対応. if(i == K - 1) break; // 辺情報(番号: E[i + 1]). int na = get<0>(t[E[i + 1]]); int nb = get<1>(t[E[i + 1]]); LL nc = get<2>(t[E[i + 1]]); // 最小値更新. // -> 頂点 na を 終端とするものを考える. if(Idx[na].count(nb)) dp[nb] = min(dp[nb], dp[na] + nc); } // 3. 出力. printf("%lld\n", (dp[N - 1] >= INF) ? -1 : dp[N - 1]); 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 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 |
[入力例] 3 4 4 1 2 2 2 3 2 1 3 3 1 3 5 4 2 1 2 [出力例] 4 ※AtCoderテストケースより [入力例] 3 2 3 1 2 1 2 3 1 2 1 1 [出力例] -1 ※AtCoderテストケースより [入力例] 4 4 5 3 2 2 1 3 5 2 4 7 3 4 10 2 4 1 4 3 [出力例] 14 ※AtCoderテストケースより [入力例] 2 3 1 1 2 3 1 2 2 1 2 1 1 [出力例] 3 [入力例] 3 4 5 1 2 2 1 3 7 2 3 4 2 3 3 2 1 3 2 4 [出力例] 5 [入力例] 7 9 10 1 2 3 2 5 4 6 7 1 3 7 5 5 6 2 3 6 1 2 4 2 2 3 1 4 7 6 3 1 4 1 5 9 2 6 5 3 [出力例] 10 [入力例] 15 21 18 1 5 2 1 3 7 1 8 5 8 9 1 3 2 6 5 7 8 2 4 5 9 4 9 9 10 6 4 6 2 4 7 1 7 6 2 7 13 3 6 10 15 6 11 1 10 11 7 13 11 7 13 14 6 11 12 8 12 14 1 14 15 2 8 9 10 1 2 3 12 7 4 6 5 7 11 13 20 18 19 21 [出力例] 21 |