結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー kukone
提出日時 2026-11-20 22:59:53
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,990 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,503 ms
コンパイル使用メモリ 393,392 KB
実行使用メモリ 1,052,056 KB
最終ジャッジ日時 2026-11-20 23:00:30
合計ジャッジ時間 13,090 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 5 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using P=pair<ll,ll>;
typedef atcoder::modint mint;
ll inf=4e18;
template<typename T, int s, int i = 0>
auto vec(const ll (&sizes)[s], const T& init = T()){
  if constexpr(i < s) return vector(sizes[i], vec<T, s, i+1>(sizes, init));
  else return init;
}


struct Edge{ll to,cost=1;};
bool operator>(Edge a,Edge b){
  return a.cost>b.cost;
}
void dijkstra(vector<vector<Edge>> &graph,ll s,vector<ll> &dis){
  priority_queue<Edge,vector<Edge>,greater<Edge>> q;
  dis=vector<ll>(graph.size(),inf);
  q.push({s,0});
  dis[s]=0;
  while(!q.empty()){
    ll f=q.top().to,c=q.top().cost;
    q.pop();
    if(dis[f]<c) continue;
    for(auto i:graph[f]){
      if(dis[i.to]<dis[f]+i.cost) continue;
      dis[i.to]=dis[f]+i.cost;
      q.push({i.to,dis[i.to]});
    }
  }
}

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll n,m,q,u,v;
  unsigned long long w;
  cin>>n>>m>>q;
  auto s=vec<ll>({n},0);
  auto g=vec<Edge>({n+1,0},{0,0});
  auto g2=vec<Edge>({128,0},{0,0});
  map<ll,ll> ma;
  for(ll i=0;i<n;i++){
    cin>>s[i];
    g[n].push_back({i,s[i]});
    g[i].push_back({n,s[i]});
  }
  for(ll i=1;i<=m;i++){
    cin>>u>>v>>w;
    if(i<=62&&w>>(62-i)==0){
      w<<=i;
    }else{
      continue;
    }
    --u,--v;
    g[u].push_back({v,(ll)w});
    g[v].push_back({u,(ll)w});
    if(!ma.contains(u)) ma[u]=i*2;
    if(!ma.contains(v)) ma[v]=i*2+1;
    g2[ma[u]].push_back({ma[v],(ll)w});
    g2[ma[v]].push_back({ma[u],(ll)w});
  }
  auto dis=vec<ll>({n+1},inf);
  auto dis2=vec<ll>({128},inf);
  dijkstra(g,n,dis);
  ll ans;
  for(ll i=0;i<q;i++){
    cin>>u>>v;
    --u,--v;
    ans=dis[u]+dis[v];
    // cout<<ans<<" ";
    if(ma.contains(u)&&ma.contains(v)){
      dijkstra(g2,ma[u],dis2);
      // cout<<dis2[ma[v]]<<" ";
      ans=min(ans,dis2[ma[v]]);
    }
    cout<<ans<<"\n";
  }
}
0