演算法 Prim’s Algorithm

#include <stdio.h>

int main()
{
    int n, m, i[201], j[201], w[201], s;
    scanf("%d%d", &n, &m);
    for (int k = 1; k <= m; k++) {
        scanf("%d%d%d", &i[k], &j[k], &w[k]);
    }
    scanf("%d", &s);

    int key[51], parent[51], finish[51], ok = 0;
    for (int k = 1; k <= n; k++) {
        key[k] = 99999;
        parent[k] = 0;
        finish[k] = 0;
    }
    key[s] = 0;

    while (ok != n) {
        int min = 99999;
        for (int k = 1; k <= n; k++) {
            if (key[k] < min && finish[k] == 0) {
                min = key[k];
                s = k;
            }
        }
        finish[s] = 1;

        for (int k = 1; k <= m; k++) {
            if (s == i[k] && key[j[k]] > w[k] && finish[j[k]] == 0){
                key[j[k]] = w[k];
                parent[j[k]] = s;
            }
            if (s == j[k] && key[i[k]] > w[k] && finish[i[k]] == 0) {
                key[i[k]] = w[k];
                parent[i[k]] = s;
            }
        }
        ok++;
    }

    printf("%d", parent[1]);
    for (int k = 2; k <= n; k++) {
        printf(" %d", parent[k]);
    }

    int sum = 0;
    for (int k = 1; k <= n; k++) {
        sum += key[k];
    }
    printf("\n%d", sum);
}