結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:08:56 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,005 bytes |
| 記録 | |
| コンパイル時間 | 2,993 ms |
| コンパイル使用メモリ | 364,364 KB |
| 実行使用メモリ | 40,004 KB |
| 最終ジャッジ日時 | 2026-11-20 23:09:21 |
| 合計ジャッジ時間 | 23,511 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 26 WA * 4 |
ソースコード
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define eb emplace_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using P = pair<ll,ll>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<P>> G(n);
vector<ll> s(n);
rep(i,0,n) cin >> s[i];
vector<int> u(m), v(m);
vector<ll> w(m);
rep(i,0,m) {
cin >> u[i] >> v[i] >> w[i];
--u[i], --v[i];
if (i < 70 && w[i] <= (2000000000000000100)>>(i+1)) {
G[u[i]].eb(v[i], w[i]<<(i+1));
G[v[i]].eb(u[i], w[i]<<(i+1));
}
}
vector<ll> dist(n, 0);
pq<P> que;
rep(i,0,n) {
dist[i] = s[i];
que.emplace(s[i], i);
}
while(!que.empty()) {
auto [c, v] = que.top();
que.pop();
if (dist[v] < c) continue;
for (auto [nv, cost] : G[v]) {
if (dist[nv] > dist[v]+cost) {
dist[nv] = dist[v]+cost;
que.emplace(dist[nv], nv);
}
}
}
vector<map<int,ll>> mp(n);
rep(s,0,n) {
que.emplace(0, s);
mp[s][s] = 0;
while(!que.empty()) {
auto [c, v] = que.top();
que.pop();
if (mp[s][v] < c) continue;
for (auto [nv, cost] : G[v]) {
if (!mp[s].contains(nv) || mp[s][nv] > c+cost) {
mp[s][nv] = c+cost;
que.emplace(c+cost, nv);
}
}
}
}
while(q--) {
int a, b;
cin >> a >> b;
--a, --b;
ll ans = dist[a]+dist[b];
if (mp[a].contains(b)) {
chmin(ans, mp[a][b]);
}
cout << ans << endl;
}
return 0;
}