J - 天空之城

由该题走过的路不消耗时间，那么我们只需要把最短路依次加入到答案中即可。

用并查集作为查询以便在 O(1) 时间内知道这片区域是否联通

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define ll long long

int n ,m;
const int N = 5e3 , M = 2e5 ;

struct G{
    int x, y;
    ll w;
    bool operator < (const G &X) const {
        return w < X.w;
    }
}g[M];

int fa[N];
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}


int main(){
    while(cin >> n >> m){
        for(int i = 1 ; i <= n ; i ++) fa[i] = i;
        unordered_map<string,int> ID;
        string a , b;
        cin >> a;
        int id = 0;
        ll x;
        for(int i = 1 ; i <= m ; i ++){
            cin >> a >> b;
            scanf("%lld",&x);
            if(ID[a] == 0) ID[a] = ++ id;
            if(ID[b] == 0) ID[b] = ++ id;
            g[i] = (G){ID[a] , ID[b] ,x } ;
        }
        sort(g+1,g+1+m);
        ll ans = 0;
        for(int i = 1 ; i <= m ; i ++){
            int fx = find(g[i].x) , fy = find(g[i].y);
            if(fx == fy) continue;
            fa[fx] = fy;
            ans += g[i].w;
        }
        x = find(fa[1]) ; 
        bool f = true;
        for(int i = 1 ; i <= n ; i ++){
            if(find(fa[i]) != x){
                puts("No!");
                f = false;
                break;
            }
        }
        if(f) printf("%lld\n",ans);
    }
    return 0;
}