結果
| 問題 |
No.1308 ジャンプビーコン
|
| コンテスト | |
| ユーザー |
 jupiro
|
| 提出日時 | 2020-12-05 19:05:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,994 bytes |
| コンパイル時間 | 2,538 ms |
| コンパイル使用メモリ | 158,812 KB |
| 最終ジャッジ日時 | 2025-01-16 18:03:33 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 TLE * 12 |
ソースコード
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>
using namespace std;
typedef long long ll;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); }return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
struct HLD {
vector<int> sz, in, out, head, par;
vector<vector<int>> g;
HLD() {}
HLD(vector<vector<int>>& _g) : g(_g), sz(_g.size()), in(_g.size()), out(_g.size()), head(_g.size()), par(_g.size()) { build(); }
void dfs_sz(int cur, int pre) {
sz[cur] = 1;
for (int& next : g[cur]) {
if (next == pre) continue;
dfs_sz(next, cur);
par[next] = cur;
sz[cur] += sz[next];
if (sz[next] > sz[g[cur][0]]) swap(next, g[cur][0]);
}
}
void dfs_hld(int cur, int pre, int& idx) {
in[cur] = idx++;
for (int& next : g[cur]) {
if (next == pre) continue;
if (next == g[cur][0]) head[next] = head[cur];
else head[next] = next;
dfs_hld(next, cur, idx);
}
out[cur] = idx;
}
void build() {
dfs_sz(0, -1);
int idx = 0;
dfs_hld(0, -1, idx);
}
void build(vector<vector<int>>& _g) {
g = _g;
sz.resize(g.size());
in.resize(g.size());
out.resize(g.size());
head.resize(g.size());
par.resize(g.size());
dfs_sz(0, -1);
int idx = 0;
dfs_hld(0, -1, idx);
}
int lca(int u, int v) {
for (;; v = par[head[v]]) {
if (in[u] > in[v]) swap(u, v);
if (head[u] == head[v]) return u;
}
}
//[l, r)の区間集合を返す
vector<pair<int, int>> path_query(int u, int v, bool edge = false) {
vector<pair<int, int>> ret;
for (;; v = par[head[v]]) {
if (in[u] > in[v]) swap(u, v);
if (head[u] == head[v]) break;
ret.emplace_back(in[head[v]], in[v] + 1);
}
ret.emplace_back(in[u] + edge, in[v] + 1);
return ret;
}
};
template< typename OperatorMonoid, typename H >
struct DualSegmentTree {
int sz, height;
vector< OperatorMonoid > lazy;
const H h;
const OperatorMonoid OM0;
DualSegmentTree(int n, const H h, const OperatorMonoid& OM0) : h(h), OM0(OM0) {
sz = 1;
height = 0;
while (sz < n) sz <<= 1, height++;
lazy.assign(2 * sz, OM0);
}
inline void propagate(int k) {
if (lazy[k] != OM0) {
lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
lazy[k] = OM0;
}
}
inline void thrust(int k) {
for (int i = height; i > 0; i--) propagate(k >> i);
}
void update(int a, int b, const OperatorMonoid& x) {
thrust(a += sz);
thrust(b += sz - 1);
for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) lazy[l] = h(lazy[l], x), ++l;
if (r & 1) --r, lazy[r] = h(lazy[r], x);
}
}
OperatorMonoid operator[](int k) {
thrust(k += sz);
return lazy[k];
}
};
template< typename OperatorMonoid, typename H >
DualSegmentTree< OperatorMonoid, H > get_dual_segment_tree(int N, const H& h, const OperatorMonoid& OM0) {
return { N, h, OM0 };
}
struct Edge {
int from, to;
ll cost;
Edge(int from, int to, ll cost) :from(from), to(to), cost(cost) {}
};
vector<ll> bfs(int st, vector<vector<pair<int, ll>>>& g) {
int n = g.size();
vector<ll> d(n, INF);
d[st] = 0;
queue<int> q; q.emplace(st);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto [nxt, len] : g[cur]) {
if (chmin(d[nxt], d[cur] + len)) {
q.emplace(nxt);
}
}
}
return d;
}
int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, kkt; cin >> n >> kkt;
ll C; cin >> C;
vector<Edge> edges; edges.reserve(n - 1);
vector<vector<int>> g(n);
vector<vector<pair<int, ll>>> tg(n);
for (int i = 0; i < n - 1; i++) {
int u, v, l; cin >> u >> v >> l;
u--; v--;
edges.emplace_back(u, v, l);
g[u].emplace_back(v);
g[v].emplace_back(u);
tg[u].emplace_back(v, l);
tg[v].emplace_back(u, l);
}
vector<vector<ll>> dist(n); for (int i = 0; i < n; i++) dist[i] = bfs(i, tg);
HLD hld(g);
auto f1 = [](ll a, ll b) {return min(a, b); };
auto f2 = [](ll a, ll b) {
return min(a, b);
};
auto lsg = get_dual_segment_tree(n, f2, INF);
vector d(kkt, lsg);
vector<int> x(kkt); for (int i = 0; i < kkt; i++) cin >> x[i], x[i]--;
d[0].update(hld.in[x[0]], hld.in[x[0]] + 1, 0);
for (int jupi = 1; jupi < kkt; jupi++) {
int cur = x[jupi];
int pre = x[jupi - 1];
for (int j = 0; j < n; j++) {
ll t = dist[pre][cur];
ll p = d[jupi - 1][hld.in[j]];
if (p == INF) continue;
d[jupi].update(hld.in[j], hld.in[j] + 1, p + t);
for (auto [l, r] : hld.path_query(pre, cur)) {
d[jupi].update(l, r, p + t);
}
for (auto [l, r] : hld.path_query(j, cur)) {
d[jupi].update(l, r, p + C + dist[j][cur]);
}
}
}
ll res = INF; for (int i = 0; i < n; i++) chmin(res, d.back()[i]);
cout << res << "\n";
}