結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:54:58 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
RE
不安定
|
| 実行時間 | - |
| コード長 | 1,977 bytes |
| 記録 | |
| コンパイル時間 | 2,487 ms |
| コンパイル使用メモリ | 357,964 KB |
| 実行使用メモリ | 9,936 KB |
| 最終ジャッジ日時 | 2026-11-20 23:55:21 |
| 合計ジャッジ時間 | 10,939 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 WA * 2 RE * 16 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
T MUL(T a, T b){
T res;
return __builtin_mul_overflow(a, b, &res)? std::numeric_limits<T>::max() : res;
}
int main(){
constexpr ll inf = 1ll << 61;
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<ll> s(n);
for(auto &&v : s) cin >> v;
m = min(m, 61);
vector<tuple<int,int,ll>> E(m);
vector<int> V;
for(int i = 0; i < m; i++){
auto &&[u, v, w] = E[i];
cin >> u >> v >> w;
u--, v--;
V.emplace_back(u);
V.emplace_back(v);
w = min(MUL(w, 1ll << (i + 1)), inf);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
int vn = V.size();
vector<vector<ll>> A(vn, vector<ll>(vn, inf));
for(int i = 0; i < m; i++){
auto [u, v, w] = E[i];
u = lower_bound(V.begin(), V.end(), u) - V.begin();
v = lower_bound(V.begin(), V.end(), v) - V.begin();
A[v][u] = A[u][v] = min(A[u][v], w);
}
for(int i = 0; i < vn; i++) A[i][i] = 0;
for(int i = 0; i < vn; i++){
for(int j = 0; j < vn; j++){
A[i][j] = min(A[i][j], s[V[i]] + s[V[j]]);
}
}
for(int k = 0; k < vn; k++){
for(int i = 0; i < vn; i++){
for(int j = 0; j < vn; j++){
A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
}
}
}
while(q--){
int a, b;
cin >> a >> b;
a--, b--;
ll ans = s[a] + s[b];
int u = lower_bound(V.begin(), V.end(), a) - V.begin();
int v = lower_bound(V.begin(), V.end(), b) - V.begin();
if(u < vn && V[u] == a && v < vn && V[v] == b){
for(int i = 0; i < vn; i++){
for(int j = 0; j < vn; j++){
ans = min(ans, A[u][i] + A[i][j] + A[j][v]);
}
}
}
cout << ans << '\n';
}
}