fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. typedef pair<int, int> ii;
  8. typedef pair<int, ii> iii;
  9. typedef vector<int> vi;
  10. typedef vector<ii> vii;
  11. typedef vector<iii> viii;
  12. vector<vii> AdjList;
  13. priority_queue< iii, vector<iii>, greater<iii> > pq;
  14. vi visited;
  15.  
  16.  
  17. int V, E, a, b, w, s, cost = 0;
  18.  
  19. void update(int edge){
  20.   visited[edge] = 1;
  21.   for (int j = 0; j < AdjList[edge].size(); j++){
  22.     ii v = AdjList[edge][j];
  23.     if (visited[v.first]==0)
  24.         pq.push(iii(v.second, ii(edge, v.first)));
  25.    }
  26. }
  27.  
  28. void prim(){
  29.   visited.assign(V+1, 0);
  30.   update(s);
  31.  
  32.   while (!pq.empty()){
  33.     iii pri = pq.top();
  34.     pq.pop();
  35.     int w = pri.first;
  36.     int a = pri.second.first;
  37.     int b = pri.second.second;
  38.  
  39.     if (visited[b]==0){
  40.       cost += w;
  41.       cout << a << " " << b << endl;
  42.     }
  43.     update(b);
  44.   }
  45. }
  46.  
  47. int main() {
  48.  
  49.  
  50.   cin >> V >> E >> s;
  51.   AdjList.assign(V+1, vii());
  52.  
  53.   for (int i = 0; i < E; i++){
  54.     cin >> a >> b >> w;
  55.     AdjList[a].push_back(ii(b, w));
  56.     AdjList[b].push_back(ii(a, w));
  57.   }
  58.  
  59.   prim();
  60.   cout << cost;
  61.  
  62. return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
5 7 0
0 1 4
0 2 4
0 3 6
0 4 6
1 2 2
2 3 8
3 4 9
stdout
copy 
0 1
1 2
0 3
0 4
18
https://ideone.com/uLG7FH
language:
C++ (gcc 8.3)
created:
2 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!