結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー HoyHoyCharhang
提出日時 2026-11-20 23:08:56
言語 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  
実行時間 -
コード長 2,005 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

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;}

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;
}
0