Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAX_N = 101; int N, E; vector<pair<int, int> > G[MAX_N]; int prim(int start) { int sum = 0; vector<int> distance; distance.resize(MAX_N); for (int i=0; i<MAX_N; i++) { distance[i] = 1000000000; //nekoj golem broj } priority_queue<pair<int, int> > pq; distance[start] = 0; pq.push({0, start}); int visited[MAX_N]; memset(visited, 0, sizeof(visited)); while (!pq.empty()) { pair<int, int> state = pq.top(); pq.pop(); int city = state.second, distance_to_city = -state.first; if (visited[city] == 0) { visited[city] = 1; sum += distance[city]; for (auto edge : G[city]) { int next = edge.first, distance_between_cities = edge.second; if (distance[next] > distance_between_cities) { distance[next] = distance_between_cities; pq.push({ -distance[next], next }); } } } } return sum; } int main() { cout << "Number of cities: " << endl; cin >> N; cout << "Number of edges: " << endl; cin >> E; cout << "Enter the edges (from, to, weight)." << endl; for (int i=0; i<E; i++) { int from, to, weight; cin >> from >> to >> weight; G[from].push_back({to, weight}); G[to].push_back({from, weight}); //bidejki grafot e nenasocen } int start = 0; //pochnuvame od temeto 0 int sum = prim(start); cout << "The minimum spanning tree has a sum of edges: " << sum << endl; return 0; }
Input data
Program output
3 3 0 1 30 0 2 60 1 2 70
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!