結果

問題 No.1442 I-wate Shortest Path Problem
コンテスト
ユーザー Nachia
提出日時 2021-03-26 22:28:22
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,269 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,475 ms
コンパイル使用メモリ 269,504 KB
最終ジャッジ日時 2025-01-19 23:00:53
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |   scanf("%d%d",&N,&K);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:42:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |     int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--;
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:51:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |     int m,c; scanf("%d%d",&m,&c);
      |              ~~~~~^~~~~~~~~~~~~~
main.cpp:55:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |       int x; scanf("%d",&x); x--;
      |              ~~~~~^~~~~~~~~
main.cpp:101:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  101 |   int Q; scanf("%d",&Q);
      |          ~~~~~^~~~~~~~~
main.cpp:103:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |     int u,v; scanf("%d%d",&u,&v); u--; v--;
      |              ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <atcoder/all>
using namespace atcoder;
#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<int> 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