求助Prim

rt。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int _ = 90005;

struct Edge { int v , w , nxt ; } e[_*2];
int head[_] , ecnt;
void Add( int u , int v , int w = 1 ) { e[ ++ecnt ] = Edge{ v , w , head[ u ] } ; head[ u ] = ecnt ; }

template< int Maxx >
struct MST {
  struct Node {
    int x , d;
    bool operator<( const Node &a ) const {
      return a.d < d;
    }
  };
  int Prim( Edge e[] , int head[] , int n ) {
    vector< int > dis( n + 5 , INT_MAX ) , vis( n + 5 );
    priority_queue< Node > Q;
    dis[ 1 ] = 0;
    int ans = 0 , cnt = 0;
    Q.push( Node{ 0 , 1 } );
    while( !Q.empty() ) {
      int x = Q.top().x , d = Q.top().d;
      Q.pop();
      if( vis[ x ] ) continue;
      cnt++;
      ans += d;
      vis[ x ] = 1;
      for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
        if( e[ i ].w < dis[ e[ i ].v ] ) {
          dis[ e[ i ].v ] = e[ i ].w;
          Q.push( Node{ e[ i ].v , dis[ e[ i ].v ] } );
        }
      }
    }
    return cnt == n ? ans : -1;
  }
};

int n , m;
MST<_> mst;

signed main() {
  cin >> n >> m;
  for( int i = 1 , u , v , w ; i <= m ; i++ ) {
    cin >> u >> v >> w;
    Add( u , v , w );
    Add( v , u , w );
  }
  int ans = mst.Prim( e , head , n );
  if( ans == -1 ) puts( "orz" );
  else cout << ans << '\n';
  return 0;
}