結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:44:58 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 3,764 bytes |
| 記録 | |
| コンパイル時間 | 4,210 ms |
| コンパイル使用メモリ | 371,560 KB |
| 実行使用メモリ | 54,708 KB |
| 最終ジャッジ日時 | 2026-11-20 23:46:00 |
| 合計ジャッジ時間 | 24,851 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 WA * 2 |
ソースコード
#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;}
class UnionFind {
public:
int n, cnt;
vector <int> par;
vector <int> siz;
UnionFind(int sz_): n(sz_), cnt(sz_), par(sz_), siz(sz_, 1) {
for (int i = 0; i < sz_; ++i) par[i] = i;
}
void init(int sz_) {
n = sz_, cnt = sz_;
par.resize(sz_);
siz.assign(sz_, 1);
for (int i = 0; i < sz_; ++i) par[i] = i;
}
int root(int x) {
if (par[x] == x) {
return x;
} else {
int r = root(par[x]);
return par[x] = r;
}
}
bool merge(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return false;
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
--cnt;
return true;
}
bool is_same(int x, int y) {
return root(x) == root(y);
}
int size(int x) {
return siz[root(x)];
}
int group_cnt() {
return cnt;
}
vector<vector<int>> groups() {
vector<vector<int>> ret(n);
for (int i = 0; i < n; ++i) {
ret[root(i)].emplace_back(i);
}
ret.erase(remove_if(ret.begin(), ret.end(), [](const vector<int> &v) {
return v.empty();
}), ret.end());
return ret;
}
};
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<ll> s(n);
rep(i,0,n) cin >> s[i];
vector<int> u(m), v(m);
vector<ll> w(m);
UnionFind uf(n);
rep(i,0,m) {
cin >> u[i] >> v[i] >> w[i];
--u[i], --v[i];
if (w[i] == 0) uf.merge(u[i], v[i]);
}
vector<vector<int>> gs = uf.groups();
vector<int> ids(n);
int l = len(gs);
rep(i,0,l) {
for (int v : gs[i]) ids[v] = i;
}
vector<ll> ns(l, 2000000000000000000);
rep(i,0,n) {
chmin(ns[ids[i]], s[i]);
}
rep(i,0,m) {
u[i] = ids[u[i]], v[i] = ids[v[i]];
}
n = l;
s = ns;
vector<vector<P>> G(n);
rep(i,0,m) if (u[i] != v[i]) {
if (w[i] > 0 && 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 (c+cost <= 3000000000000000000) {
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;
a = ids[a], b = ids[b];
if (a == b) {
cout << 0 << endl;
continue;
}
ll ans = s[a]+s[b];
if (mp[a].contains(b)) {
chmin(ans, mp[a][b]);
}
for (auto [v1, c1] : mp[a]) for (auto [v2, c2] : mp[b]) {
chmin(ans, c1+c2+s[v1]+s[v2]);
}
cout << ans << endl;
}
return 0;
}