Untitled
unknown
c_cpp
2 years ago
1.6 kB
5
Indexable
/* **************MST**************** Minimum spanning tree */ #include <bits/stdc++.h> using namespace std; struct Edge { int s, d, w; }; struct Node { int id, val; }; struct compKey { bool operator()(Node n1, Node n2) { return n1.val > n2.val; } }; void prims(vector<Edge> g[], int V) { priority_queue<Node, vector<Node>, compKey> pq; int par[V], visited[V], weight[V]; for (int i = 0; i < V; i++) { par[i] = -1; visited[i] = 0; weight[i] = 9999; } Node root = {0, 0}; weight[root.id] = 0; pq.push(root); while (!pq.empty()) { Node src = pq.top(); pq.pop(); int u = src.id; visited[u] = 1; vector<Edge> adj = g[u]; for (Edge e: adj) { int v = e.d; if (visited[v] == 0 && e.w < weight[v]) { par[v] = u; weight[v] = e.w; pq.push({v, weight[v]}); } } } int cost = 0; cout << "------------MST-------------" << endl; for (int i = 0; i < V; i++) { if (par[i] == -1)continue; cout << i << "----" << par[i] << endl; cost += weight[i]; } cout << "Cost: " << cost << endl; } int main() { int V, E; cin >> V >> E; vector<Edge> G[V]; for (int i = 0; i < E; i++) { int a, b, c; cin >> a >> b >> c; //start.direction,weight G[a].push_back({a, b, c}); G[b].push_back({b, a, c}); } prims(G, V); return 0; }
Editor is loading...