Submission #996482

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

vector<vector<pair<int, int64_t>>> mct;

int64_t dfs(int p, int s, int t) {
  if (s == t) return -1;
  int64_t res = 0;
  for (auto e : mct[s]) {
    if (e.first == p) continue;
    auto r = dfs(s, e.first, t);
    if (r == 0) continue;
    res = max(res, max(e.second, r));
  }
  return res;
}

int main() {
  int n, m, q;
  cin >> n >> m;
  vector<vector<pair<int, int64_t>>> graph(n);
  mct.resize(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a - 1].emplace_back(b - 1, c);
    graph[b - 1].emplace_back(a - 1, c);
  }
  priority_queue<tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<tuple<int64_t, int, int>>> que;
  for (auto& e : graph[0]) que.emplace(e.second, 0, e.first);
  vector<bool> used(n);
  used[0] = true;
  int64_t sum = 0;
  while (!que.empty()) {
    auto e = que.top();
    que.pop();
    if (used[get<2>(e)]) continue;
    used[get<2>(e)] = true;
    mct[get<1>(e)].emplace_back(get<2>(e), get<0>(e));
    mct[get<2>(e)].emplace_back(get<1>(e), get<0>(e));
    sum += get<0>(e);
    for (auto& d : graph[get<2>(e)]) {
      que.emplace(d.second, get<2>(e), d.first);
    }
  }
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int s, t;
    cin >> s >> t;
    cout << sum - dfs(-1, s - 1, t - 1) << endl;
  }
}

Submission Info

Judge Result