結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー mugen_1337mugen_1337
提出日時 2021-03-27 02:51:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 535 ms / 3,000 ms
コード長 7,068 bytes
コンパイル時間 3,125 ms
コンパイル使用メモリ 230,480 KB
実行使用メモリ 42,644 KB
最終ジャッジ日時 2024-11-29 06:37:37
合計ジャッジ時間 10,539 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 7 ms
5,248 KB
testcase_03 AC 36 ms
5,248 KB
testcase_04 AC 7 ms
5,248 KB
testcase_05 AC 5 ms
5,248 KB
testcase_06 AC 36 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 32 ms
5,248 KB
testcase_09 AC 11 ms
5,248 KB
testcase_10 AC 39 ms
5,248 KB
testcase_11 AC 36 ms
5,248 KB
testcase_12 AC 321 ms
31,676 KB
testcase_13 AC 186 ms
30,208 KB
testcase_14 AC 233 ms
29,440 KB
testcase_15 AC 229 ms
30,848 KB
testcase_16 AC 324 ms
31,688 KB
testcase_17 AC 495 ms
35,644 KB
testcase_18 AC 527 ms
35,524 KB
testcase_19 AC 355 ms
32,196 KB
testcase_20 AC 533 ms
35,524 KB
testcase_21 AC 535 ms
35,528 KB
testcase_22 AC 171 ms
37,524 KB
testcase_23 AC 317 ms
42,644 KB
testcase_24 AC 143 ms
30,932 KB
testcase_25 AC 303 ms
34,364 KB
testcase_26 AC 133 ms
31,192 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.cpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    size_t size(){
        return g.size();
    }
    void resize(int k){
        g.resize(k);
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};

struct HLD{
    vector<vector<int>> g;
    // u以下の部分木->[in[u],out[u])
    vector<int> sz,in,out,head,rev,par,dep;
    
    HLD(vector<vector<int>> g):
        g(g),sz(g.size()),in(g.size()),out(g.size()),head(g.size()),rev(g.size()),par(g.size()){}
    
    void build(){
 
        sz.assign(g.size(),0);
        in.assign(g.size(),0);
        out.assign(g.size(),0);
        head.assign(g.size(),0);
        rev.assign(g.size(),0);
        par.assign(g.size(),0);
        dep.assign(g.size(),0);
        dfs_sz(-1,0,0);
        int t=0;
        dfs_hld(-1,0,t);
    }
 
    int la(int v,int k){
        while(true){
            int u=head[v];
            if(in[v]-k>=in[u]) return rev[in[v]-k];
            k-=in[v]-in[u]+1;
            v=par[u];
        }
    }
 
    int lca(int u,int v){
        for(;;v=par[head[v]]){
            /* heavyな辺から先に訪問している
               訪問順が遅い方を上げていけばlcaを超えない*/
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) return u;
        }
    }
 
    int dis(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
 
    /*
    u-v のパスに関するクエリ
    ti: 元的な，ll付けるの忘れない
    q: パスの区間の求値関数，だいたいq(u,v)=seg.query(u,v)
    f: パスごとの結果をマージしていく関数
    */
    template<typename E,typename Q,typename F>
    E query(int u,int v,const E &ti,const Q &q,const F &f,bool edge=false){
        E l=ti,r=ti;
        for(;;v=par[head[v]]){
            if(in[u]>in[v]) swap(u,v),swap(l,r);
            if(head[u]==head[v]) break;
            l=f(q(in[head[v]],in[v]+1),l);
        }
        return f(f(q(in[u]+edge,in[v]+1),l),r);
    }
 
    template<typename Q>
    void add_path(int u,int v,const Q &q,bool edge=false){
        for(;;v=par[head[v]]){
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) break;
            q(in[head[v]],in[v]+1);
        }
        q(in[u]+edge,in[v]+1);
    }
 
    void dfs_sz(int pre,int now,int d){
        dep[now]=d;
        par[now]=pre;
        sz[now]=1;
        if(g[now].size() and g[now][0]==pre) swap(g[now][0],g[now].back());
        for(auto &to:g[now])if(to!=pre){
            dfs_sz(now,to,d+1);
            sz[now]+=sz[to];
            // 0がheavyな辺の先
            if(sz[g[now][0]]<sz[to]) swap(g[now][0],to);
        }
    }
    void dfs_hld(int pre,int now,int &times){
        in[now]=times++;
        rev[in[now]]=now;
        for(auto &to:g[now])if(to!=pre){
            // lightな辺は分割され，headはtoになる
            head[to]=(g[now][0]==to?head[now]:to);
            dfs_hld(now,to,times);
        }
        out[now]=times;
    }
};

template<typename T>
vector<vector<T>> WarshallFloyd(vector<vector<T>> mat, T inf=1000000100){
    int n=(int)mat.size();
    for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
    if(mat[i][k]<inf and mat[k][j]<inf) mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
    return mat;
}


signed main(){
    int N,K;cin>>N>>K;
    Graph<ll> T(N);
    vector<vector<int>> tmp(N);
    rep(i,N-1){
        int u,v;ll c;cin>>u>>v>>c;u--,v--;
        tmp[u].push_back(v);
        tmp[v].push_back(u);
        T.add_edge(u,v,c);
    }

    HLD LCA(tmp);
    LCA.build();

    vector<ll> d_T(N,LINF);
    function<void(int,int)> dfs=[&](int pre,int cur){
        for(auto &e:T[cur])if(e!=pre){
            d_T[e]=d_T[cur]+e.w;
            dfs(cur,e);
        }
    };
    d_T[0]=0;
    dfs(-1,0);


    vector<vector<ll>> d_P(K,vector<ll>(N,LINF));
    vector<ll> P(K);
    vector<vector<int>> X(K);
    rep(i,K){
        int M;cin>>M>>P[i];
        rep(j,M){
            int x;cin>>x;x--;
            X[i].push_back(x);
        }
    }

    using PP=pair<ll,int>;
    
    rep(i,K){
        priority_queue<PP,vector<PP>,greater<PP>> que;
        for(auto &st:X[i]){
            d_P[i][st]=0;
            que.emplace(0,st);
        }

        while(!que.empty()){
            auto [cur_d,cur]=que.top();que.pop();
            if(d_P[i][cur]<cur_d) continue;
            for(auto &e:T[cur])if(chmin(d_P[i][e],d_P[i][cur]+e.w)) que.emplace(d_P[i][e],e);
        }
    }

    vector<vector<ll>> MAT_K(K,vector<ll>(K,LINF));
    rep(i,K)rep(j,K){
        if(i==j) MAT_K[i][j]=P[i];
        rep(k,N){
            chmin(MAT_K[i][j],d_P[i][k]+d_P[j][k]+P[i]+P[j]);
        }
    }

    rep(k,K)rep(i,K)rep(j,K) chmin(MAT_K[i][j],MAT_K[i][k]+MAT_K[k][j]-P[k]);

    int Q;cin>>Q;
    while(Q--){
        int u,v;cin>>u>>v;u--,v--;
        ll res=LINF;
        {
            int par=LCA.lca(u,v);
            chmin(res,d_T[u]+d_T[v]-2*d_T[par]);
        }

        rep(i,K)rep(j,K) chmin(res,d_P[i][u]+MAT_K[i][j]+d_P[j][v]);

        cout<<res<<"\n";
    }

    return 0;
}
0