Submission #996871

---

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 = 500000;
    int a[N], b[N], c[N], id[N], p[N];
     
    int cc(int x, int y) {
    	return c[x] < c[y];
    }
     
    int main() {
    	//freopen("x.in", "r", stdin);
     
    	cin >> n >> m;
    	F0(i, m) cin >> a[i] >> b[i] >> c[i];
    	F0(i, m) id[i] = i;
    	sort(id, id + m, cc);
     
    	int Q, S, T;
    	cin >> Q;
    	while (Q--) {
    		cin >> S >> T;
    		F1(i, n) p[i] = i;
    		p[T] = S;
    		int disc = n - 2;
    		ll ans = 0;
    		F0(uu, m) {
   int i = id[uu];
    			if (!disc) break;
    			int x = a[i];
    			int y = b[i];
    			while (x != p[x]) x = p[x];
    			while (y != p[y]) y = p[y];
    			if (x == y) continue;
    			ans += c[i];
    			if (rand() & 1) p[x] = y; else p[y] = x;
    		}
    		cout << ans << endl;
    	}
    	
    	return 0;
    }

Submission Info

Judge Result