結果
問題 |
No.1308 ジャンプビーコン
|
ユーザー |
![]() |
提出日時 | 2020-12-04 18:59:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,747 bytes |
コンパイル時間 | 873 ms |
コンパイル使用メモリ | 60,148 KB |
最終ジャッジ日時 | 2025-01-16 15:57:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:2:10: fatal error: testlib.h: No such file or directory 2 | #include "testlib.h" | ^~~~~~~~~~~ compilation terminated.
ソースコード
#include <bits/stdc++.h> #include "testlib.h" using namespace std; using P = pair<int, int>; const long long LM = 1LL << 60; // begin constraints const int MIN_N = 2; const int MAX_N = 3000; const int MIN_Q = 2; const int MAX_Q = 3000; const int MIN_C = 1; const int MAX_C = 1000000000; const int MIN_L = 1; const int MAX_L = 1000000000; // end constraints class union_find { int num; vector<int> par, rank; public: union_find(int n) : num(n), par(vector<int>(n)), rank(vector<int>(n)) { for (int i = 0; i < n; ++i) par[i] = i; } private: int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); } public: bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; --num; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } return true; } }; vector<vector<P>> edge; long long dfs(int p, int par, int to) { if (p == to) return 0; for (auto& e : edge[p]) { if (e.second == par) continue; long long d = dfs(e.second, p, to) + e.first; if (d < LM) return d; } return LM; } vector<long long> dp; long long dfs(int p, int par, long long l, long long ds) { dp[p] += min(l, ds); for (auto& e : edge[p]) { if (e.second == par) continue; dp[p] = min(dp[p], dfs(e.second, p, l + e.first, ds)); } return dp[p]; } int main(int argc, char** argv) { registerValidation(argc, argv); int n = inf.readInt(MIN_N, MAX_N, "N"); inf.readSpace(); int q = inf.readInt(MIN_Q, MAX_Q, "Q"); inf.readSpace(); int c = inf.readInt(MIN_C, MAX_C, "C"); inf.readEoln(); edge = vector<vector<P>>(n); union_find uf(n); for (int i = 0; i < n - 1; ++i) { int u = inf.readInt(1, n, "U"); inf.readSpace(); int v = inf.readInt(1, n, "V"); inf.readSpace(); int l = inf.readInt(MIN_L, MAX_L, "L"); inf.readEoln(); --u; --v; ensure(uf.unite(u, v)); edge[u].emplace_back(l, v); edge[v].emplace_back(l, u); } vector<int> x = inf.readInts(q, 1, n, "X"); inf.readEoln(); for (int i = 0; i < q - 1; ++i) { ensure(x[i] != x[i + 1]); } inf.readEof(); for (int i = 0; i < q; ++i) { --x[i]; } dp = vector<long long>(n, LM); dp[x[0]] = 0; for (int i = 1; i < q; ++i) { long long d = dfs(x[i - 1], -1, x[i]); dfs(x[i], -1, c, d); } long long ans = LM; for (int i = 0; i < n; ++i) { ans = min(ans, dp[i]); } cout << ans << '\n'; return 0; }