Submission #996795

---

Source Code Expand

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F0(i,n) for (int i = 0; i < n; i++)
#define F1(i,n) for (int i = 1; i <= n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const double eps = 1e-10;
const int inf = 1000000009;
int i, j, k, m, n, l;
int ans;
string s;
const int N = 5000;
int a[N], b[N], id[N], p[N];
int c[N][N], u[N];


int main() {
	//freopen("x.in", "r", stdin);

	cin >> n >> m;
	F0(i, m) {
		cin >> a[i] >> b[i] >> j;
		c[a[i]][b[i]] = c[b[i]][a[i]] = j;
 	}

	int Q, S, T;
	cin >> Q;
	while (Q--) {
		cin >> S >> T;

		set<pii> SE;
		F1(i, n) if (i != S && i != T) {
			if (c[S][i]) SE.insert(pii(c[S][i], i));
			if (c[T][i]) SE.insert(pii(c[T][i], i));
			u[i] = 0;
		}

		ll ans = 0;
		F0(i, n - 2) {
			pii p = *SE.begin(); SE.erase(SE.begin());
			while (u[p.second]) {
				p = *SE.begin(); SE.erase(SE.begin());
			}
			ans += p.first;
			u[p.second] = 1;
			F1(i, n) if (i != S && i != T) {
				if (c[p.second][i]) SE.insert(pii(c[p.second][i], i));
			}

		}
		cout << ans << endl;
	}
	
	return 0;
}

Submission Info

Judge Result