結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー 👑 NachiaNachia
提出日時 2021-05-04 23:51:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,220 bytes
コンパイル時間 3,233 ms
コンパイル使用メモリ 230,428 KB
実行使用メモリ 38,328 KB
最終ジャッジ日時 2024-07-23 18:49:31
合計ジャッジ時間 15,655 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 5 ms
6,944 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 13 ms
6,944 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 177 ms
26,812 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 197 ms
27,160 KB
testcase_23 WA -
testcase_24 AC 134 ms
26,532 KB
testcase_25 AC 320 ms
35,876 KB
testcase_26 AC 154 ms
32,136 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<class E>
using dijkstra_queue = priority_queue<E,vector<E>,greater<E>>;

struct Edge{ int to; ll d; };

int N,K;
vector<vector<Edge>> E;
vector<ll> D;
vector<int> qD;
vector<vector<int>> P;
vector<vector<ll>> DK;
vector<ll> CK;

vector<vector<Edge>> E2;

int lca(int u,int v){
  if(qD[u]<qD[v]) swap(u,v);
  for(int d=17; d>=0; d--) if((qD[u]-qD[v])>=(1<<d)) u=P[d][u];
  if(u==v) return u;
  for(int d=17; d>=0; d--) if(P[d][u]!=P[d][v]){ u=P[d][u]; v=P[d][v]; }
  return P[0][u];
}

ll dist(int u,int v){
  int g=lca(u,v);
  return D[v]+D[u]-2*D[g];
}

int main(){
  scanf("%d%d",&N,&K);
  E.resize(N);
  E2.resize(N+K*2);
  rep(i,N-1){
    int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--;
    E[a].push_back({b,c});
    E[b].push_back({a,c});
    E2[a].push_back({b,c});
    E2[b].push_back({a,c});
  }

  CK.resize(K);
  rep(k,K){
    int m,c; scanf("%d%d",&m,&c);
    CK[k]=c;
    E2[N+k].push_back({N+K+k,c});
    rep(i,m){
      int x; scanf("%d",&x); x--;
      E2[x].push_back({N+k,0});
      E2[N+K+k].push_back({x,0});
    }
  }

  P.assign(18,vector<int>(N,-1));
  D.assign(N,0);
  qD.assign(N,0);

  {
    queue<int> Q;
    Q.push(0);
    while(Q.size()){
      int p=Q.front(); Q.pop();
      for(Edge e:E[p]) if(P[0][p]!=e.to){
        P[0][e.to]=p;
        D[e.to]=D[p]+e.d;
        qD[e.to]=qD[p]+1;
        Q.push(e.to);
      }
    }
    P[0][0]=0;
    rep(d,17) rep(i,N) P[d+1][i]=P[d][P[d][i]];
  }

  DK.assign(K,vector<ll>(N+K*2,1001001001001001001));
  {
    dijkstra_queue<pair<ll,int>> G;
    rep(k,K){
      DK[k][N+K+k]=0; G.push({0,N+K+k});
      while(G.size()){
        int p=G.top().second;
        ll d=G.top().first;
        G.pop();
        if(DK[k][p]!=d) continue;
        for(Edge e:E2[p]){
          int nd=d+e.d;
          if(DK[k][e.to]<=nd) continue;
          DK[k][e.to]=nd;
          G.push({nd,e.to});
        }
      }
    }
  }

  int Q; scanf("%d",&Q);
  rep(i,Q){
    int u,v; scanf("%d%d",&u,&v); u--; v--;
    ll ans=dist(u,v);
    rep(k,K) ans=min(ans,DK[k][u]+DK[k][v]+CK[k]);
    printf("%lld\n",ans);
  }
  return 0;
}
0