ARC 029-C 高橋君と国家

ARC029C_Prim.cpp

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
#define int long long
 
struct Edge{
 
   int to, c;
   bool operator<(const Edge& hoge)const{
      return c>hoge.c;
   }
};
 
vector<Edge> g[100000+1];
int used[100000+1];
 
signed main(){
 
   int N, M;
   cin>> N>> M;
   for(int i=0; i<N; i++){
      int c;
      cin>> c;
      g[i].push_back(Edge{N, c});
      g[N].push_back(Edge{i, c});
   }
   for(int i=0; i<M; i++){
      int a, b, r;
      cin>> a>> b>> r;
      a--; b--;
      g[a].push_back(Edge{b, r});
      g[b].push_back(Edge{a, r});
   }
 
   priority_queue<Edge> Q;
   for(auto e: g[0]) Q.push(e);
   used[0]=1;
   int c=0;
   while(!Q.empty()){
      auto e=Q.top(); Q.pop();
      if(used[e.to]) continue;
      c+=e.c;
      used[e.to]=1;
      for(auto ne: g[e.to]){
         if(used[ne.to]) continue;
         Q.push(ne);
      }
   }
 
   cout<< c<< endl;
 
   return 0;
}