結果
| 問題 | No.1308 ジャンプビーコン |
| ユーザー |
 hitonanode
|
| 提出日時 | 2020-12-05 00:36:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3,560 ms / 4,000 ms |
| コード長 | 8,842 bytes |
| コンパイル時間 | 2,978 ms |
| コンパイル使用メモリ | 226,064 KB |
| 最終ジャッジ日時 | 2025-01-16 16:27:34 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lint = long long;using pint = pair<int, int>;using plint = pair<lint, lint>;struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;#define ALL(x) (x).begin(), (x).end()#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template <typename T, typename V>void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());return vec; }template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }#if __cplusplus >= 201703Ltemplate <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); returnis; }template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { std::apply([&os](auto &&... args) { ((os << args << ','), ...);},tpl); return os; }#endiftemplate <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os;}template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ',';os << '}'; return os; }template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os;}template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}';return os; }template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')';return os; }template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp)os << v.first << "=>" << v.second << ','; os << '}'; return os; }#ifdef HITONANODE_LOCAL#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl#else#define dbg(x) {}#endif// lowest common ancestor (LCA) class for undirected weighted tree// 無向重み付きグラフの最小共通祖先// <https://yukicoder.me/submissions/392383>struct UndirectedWeightedTree {using T = long long; // Arbitrary data structure (operator+, operator- must be defined)int INVALID = -1;int V, lgV;int E;int root;std::vector<std::vector<std::pair<int, int>>> adj; // (nxt_vertex, edge_id)// vector<pint> edge; // edges[edge_id] = (vertex_id, vertex_id)std::vector<T> weight; // w[edge_id]std::vector<int> par; // parent_vertex_id[vertex_id]std::vector<int> depth; // depth_from_root[vertex_id]std::vector<T> acc_weight; // w_sum_from_root[vertex_id]void _fix_root_dfs(int now, int prv, int prv_edge_id) {par[now] = prv;if (prv_edge_id != INVALID) acc_weight[now] = acc_weight[prv] + weight[prv_edge_id];for (auto nxt : adj[now])if (nxt.first != prv) {depth[nxt.first] = depth[now] + 1;_fix_root_dfs(nxt.first, now, nxt.second);}}UndirectedWeightedTree() = default;UndirectedWeightedTree(int N) : V(N), E(0), adj(N) {lgV = 1;while (1 << lgV < V) lgV++;}void add_edge(int u, int v, T w) {adj[u].emplace_back(v, E);adj[v].emplace_back(u, E);// edge.emplace_back(u, v);weight.emplace_back(w);E++;}void fix_root(int r) {root = r;par.resize(V);depth.resize(V);depth[r] = 0;acc_weight.resize(V);acc_weight[r] = 0;_fix_root_dfs(root, INVALID, INVALID);}std::vector<std::vector<int>> doubling;void doubling_precalc() {doubling.assign(lgV, std::vector<int>(V));doubling[0] = par;for (int d = 0; d < lgV - 1; d++)for (int i = 0; i < V; i++) {if (doubling[d][i] == INVALID)doubling[d + 1][i] = INVALID;elsedoubling[d + 1][i] = doubling[d][doubling[d][i]];}}int kth_parent(int x, int k) {if (depth[x] < k) return INVALID;for (int d = 0; d < lgV; d++) {if (x == INVALID) return INVALID;if (k & (1 << d)) x = doubling[d][x];}return x;}int lowest_common_ancestor(int u, int v) {if (depth[u] > depth[v]) std::swap(u, v);v = kth_parent(v, depth[v] - depth[u]);if (u == v) return u;for (int d = lgV - 1; d >= 0; d--) {if (doubling[d][u] != doubling[d][v]) u = doubling[d][u], v = doubling[d][v];}return par[u];}T path_length(int u, int v) {// Not distance, but the sum of weightsint r = lowest_common_ancestor(u, v);return (acc_weight[u] - acc_weight[r]) + (acc_weight[v] - acc_weight[r]);}};template <typename T> struct ShortestPath {int V, E;int INVALID = -1;std::vector<std::vector<std::pair<int, T>>> to;ShortestPath() = default;ShortestPath(int V) : V(V), E(0), to(V) {}void add_edge(int s, int t, T len) {assert(0 <= s and s < V);assert(0 <= t and t < V);to[s].emplace_back(t, len);E++;}std::vector<T> dist;std::vector<int> prev;// Dijkstra algorithm// Complexity: O(E log E)void Dijkstra(int s) {assert(0 <= s and s < V);dist.assign(V, std::numeric_limits<T>::max());dist[s] = 0;prev.assign(V, INVALID);using P = std::pair<T, int>;std::priority_queue<P, std::vector<P>, std::greater<P>> pq;pq.emplace(0, s);while (!pq.empty()) {T d;int v;std::tie(d, v) = pq.top();pq.pop();if (dist[v] < d) continue;for (auto nx : to[v]) {T dnx = d + nx.second;if (dist[nx.first] > dnx) {dist[nx.first] = dnx, prev[nx.first] = v;pq.emplace(dnx, nx.first);}}}}};int main(){int N, Q, C;cin >> N >> Q >> C;UndirectedWeightedTree tree(N);ShortestPath<lint> sp_(N);REP(i, N - 1) {int u, v, w;cin >> u >> v >> w;u--, v--;tree.add_edge(u, v, w);sp_.add_edge(u, v, w), sp_.add_edge(v, u, w);}vector D(N, vector<lint>(N));REP(i, N) {tree.fix_root(i);D[i] = tree.acc_weight;}vector<int> X(Q);for (auto &x : X) {cin >> x;x--;}vector<lint> dnow(N, 1e18);dnow[X[0]] = 0;FOR(t, 1, Q) {auto sp = sp_;const int now = X[t - 1];const int nxt = X[t];REP(i, N) sp.add_edge(now, i, dnow[i] - dnow[now] + C);sp.Dijkstra(now);REP(i, N) sp.dist[i] += dnow[now];REP(i, N) dnow[i] = min(D[nxt][i] + sp.dist[i], dnow[i] + D[now][nxt]);}cout << *min_element(ALL(dnow)) << '\n';}