結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:27:50 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,053 bytes |
| 記録 | |
| コンパイル時間 | 5,413 ms |
| コンパイル使用メモリ | 395,700 KB |
| 実行使用メモリ | 1,314,308 KB |
| 最終ジャッジ日時 | 2026-11-20 23:28:13 |
| 合計ジャッジ時間 | 12,178 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | WA * 5 MLE * 2 -- * 23 |
ソースコード
#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;
}
__int128_t INF=4e30;
struct Edge{ll to;__int128_t cost=1;};
bool operator>(Edge a,Edge b){
return a.cost>b.cost;
}
void dijkstra(vector<vector<Edge>> &graph,ll s,vector<__int128_t> &dis){
priority_queue<Edge,vector<Edge>,greater<Edge>> q;
dis=vector<__int128_t>(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,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;
__int128_t w2=w;
if(i<=61&&w2>>(61-i)==0){
w<<=i;
}else{
continue;
}
--u,--v;
g[u].push_back({v,w2});
g[v].push_back({u,w2});
if(!ma.contains(u)) ma[u]=i*2;
if(!ma.contains(v)) ma[v]=i*2+1;
g2[ma[u]].push_back({ma[v],w2});
g2[ma[v]].push_back({ma[u],w2});
}
auto dis=vec<__int128_t>({n+1},inf);
auto dis2=vec<__int128_t>({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]]<<" ";
if(ans>dis2[ma[v]]) ans=dis2[ma[v]];
}
cout<<ans<<"\n";
}
}