結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー HoyHoyCharhang
提出日時 2026-11-20 23:49:43
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,823 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,638 ms
コンパイル使用メモリ 369,032 KB
実行使用メモリ 49,504 KB
最終ジャッジ日時 2026-11-20 23:50:36
合計ジャッジ時間 23,717 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#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);
  // 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);
  //     }
  //   }
  // }
  pq<P> que;
  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];
    for (auto [v1, c1] : mp[a]) for (auto [v2, c2] : mp[b]) {
      if (v1 == v2) {
        chmin(ans, c1+c2);
      } else {
        chmin(ans, c1+c2+s[v1]+s[v2]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}
0