結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 22:32:54 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,158 bytes |
| 記録 | |
| コンパイル時間 | 5,528 ms |
| コンパイル使用メモリ | 388,940 KB |
| 実行使用メモリ | 1,051,936 KB |
| 最終ジャッジ日時 | 2026-11-20 22:33:10 |
| 合計ジャッジ時間 | 12,608 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 3 WA * 2 MLE * 1 -- * 24 |
ソースコード
#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=9e18;
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]});
}
}
}
vector<ll> _dis;
ll dijkstra2(vector<vector<Edge>> &graph,ll s,ll g){
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]});
}
}
return _dis[g];
}
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>({n,0},{0,0});
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(w>>(63-i)==0){
w<<=i;
}else{
continue;
}
--u,--v;
g[u].push_back({v,(ll)w});
g[v].push_back({u,(ll)w});
g2[u].push_back({v,(ll)w});
g2[v].push_back({u,(ll)w});
}
auto dis=vec<ll>({n+1},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<<min(ans,dijkstra2(g2,u,v))<<"\n";
}
}