Prim's
user_3763047219
c_cpp
3 years ago
1.6 kB
4
Indexable
#include <iostream> int main() { int n = 0, m = 0; static int E[201][2] = {}; float w[201] = {}; int s = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %f", &E[i][0], &E[i][1], &w[i]); } scanf("%d", &s); int v[51] = { 0 }; v[s] = 1; float key[51] = {}; for (int i = 1; i <= n; i++) { key[i] = 999999; } key[s] = 0; int parent[51] = { 0 }; for (int j = 1; j <= m; j++) { for (int i = 1; i <= m; i++) { if (E[i][0] == s) { if (v[E[i][1]] == 0) { if (key[E[i][1]] > w[i]) { key[E[i][1]] = w[i]; parent[E[i][1]] = s; } } } else if (E[i][1] == s) { if (v[E[i][0]] == 0) { if (key[E[i][0]] > w[i]) { key[E[i][0]] = w[i]; parent[E[i][0]] = s; } } } } float minkey = 999999; for (int i = 1; i <= n; i++) { if (v[i] == 0) { if (minkey > key[i]) { minkey = key[i]; s = i; } } } v[s] = 1; } int sum = 0; for (int i = 1; i <= n; i++) { sum = sum + key[i]; } std::cout << sum; std::cout << "\n"; for (int i = 1; i < n; i++) { std::cout << parent[i] << " "; } std::cout << parent[n]; }
Editor is loading...