Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #define ii pair<int, int>
- #define iii pair<ii, int>
- using namespace std;
- struct Grafo
- {
- vector <vector <ii> > adj;
- void leer()
- {
- int nodos, aristas, f, t, w, s;
- cin >> nodos >> aristas;
- adj = vector <vector <ii> > (nodos+1, vector <ii>());
- for(int i=0; i<aristas; i++)
- {
- cin >> f >> t >> w;
- adj[f].push_back(ii(w, t));
- adj[t].push_back(ii(w, f));
- }
- cin >> s;
- vector <bool> v(nodos+1, false);
- priority_queue <iii, vector <iii>, greater<iii> > pq;
- vector <iii> res;
- for(int i=0; i<adj[s].size(); i++)
- pq.push(make_pair(adj[s][i], s));
- v[s] = 1;
- int usados = 0;
- while(usados < nodos-1)
- {
- iii p = pq.top();
- pq.pop();
- int n = p.first.second;
- if(!v[n])
- {
- usados++;
- v[n] = true;
- res.push_back(p);
- for(int i=0; i<adj[n].size(); i++)
- if(!v[adj[n][i].second])
- pq.push(make_pair(adj[n][i], n));
- }
- }
- int mst = 0;
- for(int i=0; i<res.size(); i++)
- mst += res[i].first.first;
- cout << mst << endl;
- }
- };
- int main()
- {
- Grafo g;
- g.leer();
- return 0;
- }
Add Comment
Please, Sign In to add comment