fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> P;
  5.  
  6. int main() {
  7. 	ios_base::sync_with_stdio(false), cin.tie(0);
  8.  
  9. 	int n, m;
  10. 	vector<P> adj[301];
  11.  
  12. 	cin >> n;
  13. 	for(int i = 1; i <= n; i++) {
  14. 		cin >> m;
  15. 		adj[0].push_back({m, i});
  16. 	}
  17. 	for(int i = 1; i <= n; i++)
  18. 		for(int j = 1; j <= n; j++) {
  19. 			cin >> m;
  20.  
  21. 			if(!m)
  22. 				continue;
  23.  
  24. 			adj[i].push_back({m, j});
  25. 		}
  26.  
  27. 	int cnt = 0, ans = 0, bias, nxt;
  28. 	vector<int> isin(n + 1, 0);
  29. 	priority_queue<P, vector<P>, greater<P>> pq;
  30.  
  31. 	isin[0] = 1;
  32. 	for(auto i : adj[0])
  33. 		pq.push(i);
  34.  
  35. 	while(cnt < n) {
  36. 		bias = pq.top().first;
  37. 		nxt = pq.top().second;
  38. 		pq.pop();
  39.  
  40. 		cout << bias << '\n';
  41.  
  42. 		if(isin[nxt])
  43. 			continue;
  44.  
  45. 		cnt++;
  46. 		ans += bias;
  47. 		isin[nxt] = 1;
  48.  
  49. 		for(auto i : adj[nxt])
  50. 			if(!isin[i.second])
  51. 				pq.push(i);
  52. 	}
  53.  
  54. 	cout << ans;
  55. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
stdout
copy 
3
2
2
2
9
https://ideone.com/YjKKPB
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

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!