結果
問題 | No.1308 ジャンプビーコン |
ユーザー |
![]() |
提出日時 | 2020-12-06 01:10:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,486 ms / 4,000 ms |
コード長 | 1,674 bytes |
コンパイル時間 | 2,327 ms |
コンパイル使用メモリ | 204,152 KB |
最終ジャッジ日時 | 2025-01-16 18:12:59 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>void chmin(T &a, T b) {if (b < a) {a = b;}}using graph = vector<vector<pair<int64_t, int64_t>>>;using grid = vector<vector<int64_t>>;using vec = vector<int64_t>;constexpr int64_t inf = 1e18;int64_t n, c;void dfs(const graph &to, vector<int64_t> &dist, int v, int par) {for (auto [next, l] : to[v]) {if (next == par) continue;dist[next] = dist[v] + l;dfs(to, dist, next, v);}}void treedp(const graph &to, const grid &dist, const vec &prev, vec &next,vec &tele, int x0, int x1, int v, int par) {tele[v] = prev[v] + c + dist[v][x1];for (auto [child, _] : to[v]) {if (child == par) continue;treedp(to, dist, prev, next, tele, x0, x1, child, v);chmin(tele[v], tele[child]);}chmin(next[v], prev[v] + dist[x0][x1]);chmin(next[v], prev[x0] + dist[x0][v] + dist[v][x1]);chmin(next[v], tele[v]);}int main() {int64_t q;cin >> n >> q >> c;graph to(n);for (int i = 0; i < n - 1; i++) {int64_t u, v, l;cin >> u >> v >> l;u--; v--;to[u].emplace_back(v, l);to[v].emplace_back(u, l);}vector<int> x(q);for (int i = 0; i < q; i++) {cin >> x[i];x[i]--;}grid dist(n, vec(n));for (int i = 0; i < n; i++) {dfs(to, dist[i], i, -1);}grid dp(q, vec(n, inf));dp[0][x[0]] = 0;vec tele(n);for (int i = 1; i < q; i++) {treedp(to, dist, dp[i - 1], dp[i], tele, x[i - 1], x[i], x[i], -1);}cout << dp[q - 1][x[q - 1]] << endl;}