結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー NOSSNOSS
提出日時 2021-03-27 10:32:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 633 ms / 3,000 ms
コード長 6,032 bytes
コンパイル時間 3,216 ms
コンパイル使用メモリ 235,344 KB
実行使用メモリ 31,028 KB
最終ジャッジ日時 2024-05-06 21:51:00
合計ジャッジ時間 13,871 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 11 ms
5,376 KB
testcase_03 AC 249 ms
5,376 KB
testcase_04 AC 14 ms
5,376 KB
testcase_05 AC 11 ms
5,376 KB
testcase_06 AC 261 ms
5,376 KB
testcase_07 AC 10 ms
5,376 KB
testcase_08 AC 232 ms
5,376 KB
testcase_09 AC 13 ms
5,376 KB
testcase_10 AC 250 ms
5,376 KB
testcase_11 AC 248 ms
5,376 KB
testcase_12 AC 435 ms
25,992 KB
testcase_13 AC 372 ms
24,832 KB
testcase_14 AC 432 ms
24,576 KB
testcase_15 AC 426 ms
25,344 KB
testcase_16 AC 475 ms
27,060 KB
testcase_17 AC 616 ms
30,892 KB
testcase_18 AC 633 ms
30,900 KB
testcase_19 AC 459 ms
26,936 KB
testcase_20 AC 589 ms
31,028 KB
testcase_21 AC 597 ms
31,028 KB
testcase_22 AC 375 ms
29,056 KB
testcase_23 AC 456 ms
30,784 KB
testcase_24 AC 364 ms
24,376 KB
testcase_25 AC 420 ms
26,780 KB
testcase_26 AC 359 ms
26,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using P = pair<int, int>;
using P3 = pair<int,P>;
using PP = pair<P, P>;
constexpr int INF32 = 1 << 30;
constexpr ll INF64 = 1LL << 62;
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};
constexpr int di8[] = {0, 1, 1, 1, 0, -1, -1, -1};
constexpr int dj8[] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr double EPS = 1e-10;
const double PI = acos(-1);

#define ALL(v) (v).begin(),(v).end()
#define REP(i,n) for(int i=0,i_len=n; i<i_len; ++i)

template<typename T1,typename T2> bool chmax(T1 &a, T2 b) { if (a<b) { a=b; return 1; } return 0; }
template<typename T1,typename T2> bool chmin(T1 &a, T2 b) { if (b<a) { a=b; return 1; } return 0; }

template <typename Monoid>
struct SegmentTree{
private:
    using F = std::function<Monoid(Monoid, Monoid)>;
    int N;
    std::vector<Monoid> node;
    F f;
    Monoid e;  // identity element

public:
    SegmentTree(){}
    SegmentTree(F f, Monoid e):f(f), e(e){}
    void init(int sz){
        N = 1;
        while(N < sz) N <<= 1;
        node.assign(2*N-1, e);
    }
    void build(std::vector<Monoid>& v){
        int sz = int(v.size());
        init(sz);
        for(int i=0; i<sz; i++){
            node[i+N-1] = v[i];
        }
        for(int i=N-2; i>=0; i--){
            node[i] = f(node[i*2+1], node[i*2+2]);
        }
    }
    void update(int k, Monoid x){
        k += N-1;
        node[k] = x;
        while(k > 0){
            k = (k-1)/2;
            node[k] = f(node[2*k+1], node[2*k+2]);
        }
    }
    // [a,b)
    Monoid query(int a, int b){return query(a, b, 0, 0, N);}
    Monoid query(int a, int b, int k, int l, int r){
        if(b <= l || r <= a) return e;
        if(a <= l && r <= b) return node[k];
        Monoid vl, vr;
        vl = query(a, b, 2*k+1, l, (l+r)/2);
        vr = query(a, b, 2*k+2, (l+r)/2, r);
        return f(vl, vr);
    }
};

template <typename T>
struct LCA {
    using P = std::pair<int,int>;
    using CostType = T;
    const int INF = 1<<30;
    struct edge {
        int from, to, rev;
        CostType cost;
        edge(int from, int to, int rev, CostType cost) : from(from), to(to), rev(rev), cost(cost){}
    };
    int V = 0;
    int root = 0;
    std::vector<std::vector<edge> > graph;
    std::vector<int> depth, vs, ds, us;  // ds[v]:go down to v, us[v]:go up from v

private:
    SegmentTree<P> rmq = SegmentTree<P>([](P a, P b){return min(a,b);},P(INF,-1));
    SegmentTree<CostType> rsq = SegmentTree<CostType>([](CostType a, CostType b){return a+b;}, 0);

    void dfs(int v, int p, int d, int &idx){
        vs[idx] = v;
        depth[v] = d;
        ds[v] = idx++;
        for(auto& e : graph[v]){
            if(e.to == p) continue;
            dfs(e.to, v, d+1, idx);
            vs[idx] = v;
            idx++;
        }
        us[v] = idx;
    }

public:
    LCA() = default;
    LCA(int V, int root = 0) : V(V), graph(V), depth(V), vs(V*2-1), ds(V), us(V), root(root){}
    void init(int n, int r = 0){
        V = n;
        graph.resize(V);
        depth.resize(V);
        vs.resize(V*2-1);
        ds.resize(V);
        us.resize(V);
        root = r;
    }
    void add_edge(int from, int to, CostType cost = 1){
        graph[from].emplace_back(edge(from,to,int(graph[to].size()),cost));
        graph[to].emplace_back(edge(to,from,int(graph[from].size())-1,cost));
    }
    void build(){
        int idx = 0;
        dfs(root, -1, 0, idx);
        std::vector<P> depv(idx);
        for(int i=0;i<idx;i++){
            depv[i] = P(depth[vs[i]], vs[i]);
        }
        rmq.build(depv);
        std::vector<CostType> cstv(idx, 0);
        for(int i=0;i<V;i++){
            for(auto& e : graph[i]){
                if(depth[e.from] < depth[e.to]){
                    cstv[ds[e.to]] = e.cost;
                    cstv[us[e.to]] = -e.cost;
                }
            }
        }
        rsq.build(cstv);
    }
    int query(int u, int v){
        return rmq.query(std::min(ds[u],ds[v]), std::max(ds[u],ds[v])+1).second;
    }
    CostType dist(int u){
        return rsq.query(ds[root], ds[u]+1);
    }
    CostType dist(int u, int v){
        int w = query(u, v);
        return dist(u) + dist(v) - 2*dist(w);
    }
    void update(int v, CostType cost){
        rsq.update(ds[v], cost);
        rsq.update(us[v], -cost);
    }
};


int solve(){
    int N, K;
    cin >> N >> K;
    LCA<ll> lca(N);
    REP(i,N-1){
        ll a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        lca.add_edge(a,b,c);
    }
    lca.build();
    vector<ll> p(K);
    vector<vector<ll> > ardt(K,vector<ll>(N,INF64)), a2a(K,vector<ll>(K,INF64));
    REP(i,K){
        int m;
        cin >> m >> p[i];
        queue<pair<int,ll> > que;
        REP(j,m){
            int x;
            cin >> x;
            x--;
            que.push(make_pair(x,0));
            ardt[i][x] = 0;
        }
        while(!que.empty()){
            auto p = que.front();
            que.pop();
            int now = p.first;
            if(ardt[i][now] < p.second) continue;
            for(auto e : lca.graph[now]){
                if(chmin(ardt[i][e.to], ardt[i][now]+e.cost)){
                    que.push(make_pair(e.to,ardt[i][e.to]));
                }
            }
        }
    }
    REP(i,K) REP(j,K) REP(k,N) chmin(a2a[i][j], ardt[i][k]+ardt[j][k]);
    REP(k,K) REP(i,K) REP(j,K){
        chmin(a2a[i][j], a2a[i][k]+a2a[k][j]+p[k]);
    }
    int Q;
    cin >> Q;
    REP(i,Q){
        int u, v;
        cin >> u >> v;
        u--; v--;
        ll res = lca.dist(u,v);
        REP(j,K) REP(k,K){
            chmin(res, ardt[j][u]+a2a[j][k]+ardt[k][v]+p[j]+(j==k?0:p[k]));
        }
        cout << res << endl;
    }
    return 0;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    // int t; cin >> t; for(int i=0;i<t;i++) solve();
    // while(!solve());
    solve();
    return 0;
}
0