結果
問題 |
No.1308 ジャンプビーコン
|
ユーザー |
|
提出日時 | 2024-04-01 15:51:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,454 ms / 4,000 ms |
コード長 | 2,613 bytes |
コンパイル時間 | 2,354 ms |
コンパイル使用メモリ | 210,044 KB |
最終ジャッジ日時 | 2025-02-20 18:55:45 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int MN = 3500; vector<ll> T(MN, 0); ll INF = (1LL << 60); struct ED { int to; ll cost; }; struct TP { ll m1 = INF;ll m2 = INF; void add(ll x) { if (x < m1) { m2 = m1;m1 = x; } else { m2 = min(m2, x); } } ll get(ll x) { return (x != m1 ? m1 : m2); } }; vector<int> PAR(MN, 0); vector<vector<ED>> G(MN); vector<vector<ll>> D(MN, vector<ll> (MN, -1)); vector<ll> dp1, dp2; void dfs(int v, int par) { dp1[v] = T[v]; PAR[v] = par; for (auto nv : G[v]) { if (nv.to == par) continue; dfs(nv.to, v); dp1[v] = min(dp1[v], min(nv.cost + T[nv.to], nv.cost + dp1[nv.to])); } } void dfs2(int v, int par) { TP tp; for (auto nv : G[v]) { if (nv.to == par) { tp.add(min(nv.cost + T[nv.to], nv.cost + dp2[v])); } else { tp.add(min(nv.cost + T[nv.to], nv.cost + dp1[nv.to])); } } for (auto nv : G[v]) { if (nv.to == par) continue; dp2[nv.to] = T[v]; ll value = min(nv.cost + T[nv.to], nv.cost + dp1[nv.to]); dp2[nv.to] = min(dp2[nv.to], tp.get(value)); dfs2(nv.to, v); } } vector<ll> solve(int N) { dp1.assign(N, INF); dp2.assign(N, INF); dfs(0, 0); dfs2(0, 0); vector<ll> ans(N, INF); for (int v = 0;v < N;v++) { ans[v] = T[v]; for (auto nv : G[v]) { ans[v] = min(ans[v], nv.cost + T[nv.to]); if (nv.to == PAR[v]) { ans[v] = min(ans[v], nv.cost + dp2[v]); } else { ans[v] = min(ans[v], nv.cost + dp1[nv.to]); } } } return ans; } int main() { int N, Q;ll C;cin >> N >> Q >> C; for (int i = 0;i < N - 1;i++) { int u, v;ll l;cin >> u >> v >> l; u--;v--; G[u].push_back({v, l}); G[v].push_back({u, l}); } vector<int> X(Q+1, -1); for (int i = 1;i <= Q;i++) cin >> X[i],X[i]--; for (int v = 0;v < N;v++) { D[v][v] = 0; queue<int> pq; pq.push(v); while (!pq.empty()) { int t = pq.front();pq.pop(); for (auto nv : G[t]) { if (D[v][nv.to] == -1) { D[v][nv.to] = D[v][t] + nv.cost; pq.push(nv.to); } } } } vector<ll> dp(N, INF); for (int v = 0;v < N;v++) { int s = X[1];int t = X[2]; dp[v] = D[s][v] + D[v][t]; } for (int i = 3;i <= Q;i++) { int s = X[i - 1]; int t = X[i]; vector<ll> ndp(N, INF); ll mins = INF; for (int v = 0;v < N;v++) { T[v] = dp[v]; mins = min(mins, dp[v]); } for (int v = 0;v < N;v++) ndp[v] = D[s][v] + D[v][t] + mins; auto res = solve(N); for (int v = 0;v < N;v++) { ndp[v] = min(ndp[v], res[v] + D[v][t] + C); ndp[v] = min(ndp[v], dp[v] + D[s][t]); } swap(dp, ndp); } ll ans = INF; for (int v = 0;v < N;v++) ans = min(ans, dp[v]); cout << ans << endl; }