Untitled
unknown
plain_text
2 years ago
1.2 kB
16
Indexable
#include <fstream> #include <climits> #include <iostream> using namespace std; ifstream fin ("prim.in"); ofstream fout ("prim.out"); const int nMAX = 100; int n, m; int mc[nMAX + 1][nMAX + 1]; int arb[nMAX + 1], arbcost; void prim(int nod) { int i, j, mini, minj, mincost, k; for (i = 1; i <= n; ++i) arb[i] = -1; arb[nod] = 0; arbcost = 0; for (k = 1; k <= n-1; ++k) { mincost = INT_MAX/2; for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) { if (arb[i] != -1 && arb[j] == -1 && mc[i][j] != 0) if (mc[i][j] < mincost) { mincost = mc[i][j]; mini = i; minj = j; } } if (mincost != INT_MAX/2) { arbcost += mincost; arb[minj] = mini; } } } int main() { int i, j, c, k, plecare; fin >> n >> m; for (k = 1; k <= m; ++k) { fin >> i >> j >> c; mc[i][j] = mc[j][i] = c; } cin >> plecare; prim(plecare); fout << arbcost << '\n'; for (k = 1; k <= n; ++k) fout << arb[k] << ' '; }
Editor is loading...