Submission #76222427

---

Source Code Expand

//#define _GLIBCXX_DEBUG
//提出の際、1行目はコメントアウトすること
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(a,b) for(ll a=0;a<b;a++)
#define rrep(a,b) for(ll a=b-1;a>=0;a--)
const long double pai=3.14159265358979323;
using Pair = pair<ll,ll>;
#define MOD 998244353
#define INF 1000000000000000000
#define MINF -1000000000000000000
using vll = vector<ll>;
#include <atcoder/all>
using namespace atcoder;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N,M,K;
    cin>>N>>M>>K;
    vector<pair<ll,Pair>> C(M);
    rep(i,M){
        ll u,v,w;
        cin>>u>>v>>w;
        u--;v--;
        C[i]={w,{u,v}};
    }

    vector<bool> E(M,0);
    rep(i,K){
        ll t;
        cin>>t;
        t--;
        E[t]=1;
    }

    dsu d(N);
    vector<pair<ll,Pair>> RC;
    ll res=K;
    ll ans=0;
    rep(i,M){
        if(E[i]){
            auto [w,tmp]=C[i];
            auto [u,v]=tmp;
            if(d.same(u,v)){cout<<-1<<endl;return 0;}
            d.merge(u,v);
            ans+=w;
        }
        else{
            RC.push_back(C[i]);
        }
    }

    sort(RC.begin(),RC.end());

    for(auto [w,tmp]:RC){
        auto [u,v]=tmp;
        if(!d.same(u,v)){d.merge(u,v);ans+=w;res++;}
    }

    if(res!=N-1){cout<<-1<<endl;return 0;}
    else{cout<<ans<<endl;}


}

Submission Info

Judge Result