Prim's

 avatar
user_3763047219
c_cpp
2 years ago
1.6 kB
0
Indexable
Never
#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];



}