Submission #996328

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF      1000000007
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int n, m, q;
int s, t;
vector<P> e[200000];
vector<PP> ee;

struct UF{
	int par[200000];
	int rank[200000];
	int si[200000];

	void init(int n){
		rep(i,n){
			par[i] = i;
			rank[i] = 0;
			si[i] = 1;
		}
	}

	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
			si[y] += si[x];
		} else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
			si[x] += si[y];
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};
UF uf;
vector<P> hoge;
bool ok[200000];

int main(){
    cin >> n >> m;
    rep(i,m){
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        e[a].push_back(P(c,b));
        e[b].push_back(P(c,b));
        ee.push_back(PP(c,P(a,b)));
    }
    uf.init(n);
    cin >> q;
    rep(i,q){
        cin >> s >> t;
        s--;
        t--;
        hoge.clear();
        memset(ok,0,sizeof(ok));
        ok[s] = true;
        ok[t] = true;
        hoge.clear();
        rep(j,n) rep(k,e[j].size()) hoge.push_back(e[s][i]);
        sort(hoge.begin(),hoge.end());
        sort(ee.begin(),ee.end());
        ll ans = 0;
        uf.init(n);
        uf.unite(s,t);
        rep(j,ee.size()){
            if(!uf.same(ee[j].second.first,ee[j].second.second)){
                ans += ee[j].first;
                uf.unite(ee[j].second.first,ee[j].second.second);
            }
        }
        cout << ans << endl;
    }
    
}

Submission Info

Judge Result