#include using namespace std; using ll = long long; #define ALL(obj) (obj).begin(),(obj).end() template using priority_queue_reverse = priority_queue,greater>; constexpr long long MOD = 1'000'000'000LL + 7; //' constexpr long long MOD2 = 998244353; constexpr long long HIGHINF = (long long)1e18; constexpr long long LOWINF = (long long)1e15; constexpr long double PI = 3.1415926535897932384626433L; template vector multivector(size_t N,T init){return vector(N,init);} template auto multivector(size_t N,T... t){return vector(N,multivector(t...));} template void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template ostream &operator<<(ostream &o, const map&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template ostream &operator<<(ostream &o, const set&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template ostream &operator<<(ostream &o, const multiset&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template ostream &operator<<(ostream &o, const vector&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template ostream &operator<<(ostream &o, const pair&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} void print(void) {cout << endl;} template void print(Head&& head) {cout << head;print();} template void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward(tail)...);} template void chmax(T& a, const T b){a=max(a,b);} template void chmin(T& a, const T b){a=min(a,b);} vector split(const string &str, const char delemiter) {vector res;stringstream ss(str);string buffer; while( getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;} int msb(int x) {return x?31-__builtin_clz(x):-1;} void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} /* * @title Graph * @docs md/graph/Graph.md */ template class Graph{ private: const size_t N,H,W; public: vector>> edges; Graph():H(-1),W(-1),N(0) {} Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {} Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {} inline void make_edge(size_t from, size_t to, T w) { edges[from].emplace_back(to,w); } //{from_y,from_x} -> {to_y,to_x} inline void make_edge(pair from, pair to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); } inline void make_bidirectional_edge(size_t from, size_t to, T w) { make_edge(from,to,w); make_edge(to,from,w); } inline void make_bidirectional_edge(pair from, pair to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); make_edge(to.first*W+to.second,from.first*W+from.second,w); } inline void resize(const size_t _N) {N=_N;edges.resize(N);} inline size_t size(){return N;} inline size_t idx(pair yx){return yx.first*W+yx.second;} }; template class TreeBuilder; template class Tree { using TypeEdge = typename Operator::TypeEdge; size_t num; size_t ord; Graph& g; friend TreeBuilder; /** * constructor * O(N) */ Tree(Graph& graph): g(graph), num(graph.size()), depth(graph.size(),-1), order(graph.size()), edge_dist(graph.size()){ } //for make_depth void dfs(int curr, int prev){ for(const auto& e:g.edges[curr]){ const int& next = e.first; if(next==prev) continue; depth[next] = depth[curr] + 1; edge_dist[next] = Operator::func_edge_merge(edge_dist[curr],e.second); dfs(next,curr); order[ord++] = next; } } /** * 寝付き木を作る * O(N) you can use anytime */ void make_root(const int root) { depth[root] = 0; edge_dist[root] = Operator::unit_edge; ord = 0; dfs(root,-1); order[ord++] = root; reverse_copy(order.begin(),order.end(),back_inserter(reorder)); } /** * 子を作る * O(N) after make_root */ void make_child(const int root = 0) { child.resize(num); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] < depth[e.first]) child[i].push_back(e); } /** * 部分木のサイズを作る * O(N) after make_child */ void make_subtree_size() { subtree_size.resize(num,1); for (size_t i:order) for (auto e : child[i]) subtree_size[i] += subtree_size[e.first]; } /** * 親を作る * O(N) after make_root */ void make_parent() { parent.resize(num,make_pair(num,Operator::unit_edge)); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] > depth[e.first]) parent[i] = e; } void make_ancestor() { ancestor.resize(num); for (size_t i = 0; i < num; ++i) ancestor[i][0] = (parent[i].first!=num?parent[i]:make_pair(i,Operator::unit_lca_edge)); for (size_t j = 1; j < Operator::bit; ++j) { for (size_t i = 0; i < num; ++i) { size_t k = ancestor[i][j - 1].first; ancestor[i][j] = Operator::func_lca_edge_merge(ancestor[k][j - 1],ancestor[i][j - 1]); } } } pair lca_impl(size_t l, size_t r) { if (depth[l] < depth[r]) swap(l, r); int diff = depth[l] - depth[r]; auto ancl = make_pair(l,Operator::unit_lca_edge); auto ancr = make_pair(r,Operator::unit_lca_edge); for (int j = 0; j < Operator::bit; ++j) { if (diff & (1 << j)) ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); } if(ancl.first==ancr.first) return ancl; for (int j = Operator::bit - 1; 0 <= j; --j) { if(ancestor[ancl.first][j].first!=ancestor[ancr.first][j].first) { ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][j],ancr); } } ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][0],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][0],ancr); return Operator::func_lca_edge_merge(ancl,ancr); } public: vector depth; vector order; vector reorder; vector subtree_size; vector> parent; vector>> child; vector edge_dist; vector,Operator::bit>> ancestor; /** * O(N) builder */ static TreeBuilder builder(Graph& graph) { return TreeBuilder(graph);} /** * O(logN) after make_ancestor * return {lca,lca_dist} l and r must be connected */ pair lca(size_t l, size_t r) {return lca_impl(l,r);} }; template class TreeBuilder { bool is_root_made =false; bool is_child_made =false; bool is_parent_made=false; public: using TypeEdge = typename Operator::TypeEdge; TreeBuilder(Graph& g):tree(g){} TreeBuilder& root(const int rt) { is_root_made=true; tree.make_root(rt); return *this;} TreeBuilder& child() { assert(is_root_made); is_child_made=true; tree.make_child(); return *this;} TreeBuilder& parent() { assert(is_root_made); is_parent_made=true; tree.make_parent(); return *this;} TreeBuilder& subtree_size() { assert(is_child_made); tree.make_subtree_size(); return *this;} TreeBuilder& ancestor() { assert(is_parent_made); tree.make_ancestor(); return *this;} Tree&& build() {return move(tree);} private: Tree tree; }; template struct TreeOperator{ using TypeEdge = T; inline static constexpr size_t bit = 20; inline static constexpr TypeEdge unit_edge = 0; inline static constexpr TypeEdge unit_lca_edge = 0; inline static constexpr TypeEdge func_edge_merge(const TypeEdge& parent,const TypeEdge& w){return parent+w;} inline static constexpr pair func_lca_edge_merge(const pair& l,const pair& r){return make_pair(l.first,l.second+r.second);} }; /** * @url https://yukicoder.me/problems/no/1308 * @est 600 */ int main() { cin.tie(0);ios::sync_with_stdio(false); long long N,Q,C; cin >> N >> Q >> C; Graph graph(N); for(int i=0;i+1> u >> v >> w; u--,v--; graph.make_bidirectional_edge(u,v,w); } vector X(Q); for(int i=0;i> X[i],X[i]--; //dp_i,j := x_iにいて、ジャンプビーコンがjにあるときの最小値。j=Nはビーコンなし。 auto dp = multivector(Q,N+1,HIGHINF); dp[0][N]=0; for(int i=1;i> tree = Tree>::builder(graph).root(X[i]).parent().child().build(); //jにあるジャンプビーコンをそのままにして、X[i]へ向かうとき for(int j=0;j<=N;++j) { chmin(dp[i][j],dp[i-1][j]+tree.edge_dist[X[i-1]]); } //jにジャンプビーコンを置いて、X[i]へ向かうとき { long long cost=tree.edge_dist[X[i-1]]; for(int j=X[i-1]; j != X[i]; j = tree.parent[j].first) { chmin(dp[i][j],dp[i-1][N]+cost); } } //ジャンプビーコンを使った後、X[i]へ向かうとき for(int j=0;j dp2(N); for(int j=0;j