結果
問題 |
No.1308 ジャンプビーコン
|
ユーザー |
![]() |
提出日時 | 2020-12-01 23:05:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 413 ms / 4,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 2,326 ms |
コンパイル使用メモリ | 202,216 KB |
最終ジャッジ日時 | 2025-01-16 12:31:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
// // AC solution (writer) // #include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll INF = 1e18; vector<vector<pair<int, int>>> e; ll dist(int x, int p, int to) { if (x == to) return 0; ll ans = INF; for (auto &ep : e[x]) { if (ep.first == p) continue; ans = min(ans, ep.second + dist(ep.first, x, to)); } return ans; } vector<ll> dp; ll dfs(int x, int p, ll d, ll l) { dp[x] += min(d, l); for (auto &ep : e[x]) { if (ep.first == p) continue; dp[x] = min(dp[x], dfs(ep.first, x, ep.second + d, l)); } return dp[x]; } int main() { int n, q, c; cin >> n >> q >> c; e = vector<vector<pair<int, int>>>(n); for (int i = 0; i < n - 1; i++) { int u, v, l; cin >> u >> v >> l; u--, v--; e[u].emplace_back(v, l); e[v].emplace_back(u, l); } vector<int> x(q); for (int i = 0; i < q; i++) { cin >> x[i]; x[i]--; } dp = vector<ll>(n, INF); dp[x[0]] = 0; for (int i = 1; i < q; i++) { ll l = dist(x[i], x[i], x[i - 1]); dfs(x[i], x[i], c, l); } cout << dp[x[q - 1]] << endl; return 0; }