fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int w[101][101];
  6.  
  7. typedef pair< int, int > pii;
  8.  
  9. priority_queue< pii, vector< pii > , greater<pii> > pq;
  10. vector< int > taken;
  11. int a[101];
  12.  
  13. int n, m;
  14.  
  15. void process( int u ){
  16.  
  17. 	taken[u]= 1;
  18.  
  19. 	for( int i= 1; i<= n; ++i ){
  20.  
  21. 		if( !taken[i] )
  22. 			pq.push( { w[u][i], i } );
  23. 	}
  24.  
  25. }
  26.  
  27. int mst(){
  28.  
  29. 	taken.assign( n+1, 0 );
  30.  
  31. 	process( 1 );
  32.  
  33. 	int mst_cost= 0;
  34.  
  35. 	while( !pq.empty() ){
  36.  
  37. 		pii front= pq.top(); pq.pop();
  38.  
  39. 		int u= front.second, w= front.first;
  40.  
  41. 		if( !taken[u] ){
  42.  
  43. 			//cout << u << " " << w << endl;
  44.  
  45. 			mst_cost+= w;
  46. 			process( u );
  47. 		}
  48.  
  49. 	}
  50.  
  51. 	return mst_cost;
  52. }
  53.  
  54. int main(){
  55.  
  56. 	scanf( "%d%d", &n, &m );
  57.  
  58. 	for( int i= 0; i< m; ++i )
  59. 		scanf( "%d", &a[i] );
  60.  
  61. 	for( int i= 1; i<= n; ++i )
  62. 		for( int j= 1; j<= n; ++j )
  63. 			scanf( "%d", &w[i][j] );
  64.  
  65. 	cout << mst() << endl;
  66.  
  67. }
Success #stdin #stdout 0s 3320KB
comments (?)
stdin
copy 
4 2
1 4
0 2 4 3
2 0 5 1
4 5 0 2
3 1 2 0
stdout
copy 
5
https://ideone.com/aHP1kL
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!