新的开始

LibreOJ-10066-新的开始

实现

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 310;
int n;
int g[N][N];
int dis[N];
bool mark[N];

int prim () {
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;

    for (int k = 1; k <= n; ++ k) {
        int cur = -1;
        for (int i = 0; i <= n; ++ i)
            if (mark[i] == false && (cur == -1 || dis[i] < dis[cur]))
                cur = i;
        mark[cur] = true;

        for (int i = 0; i <= n; ++ i) {
            if (mark[i] == true) continue;
            dis[i] = min(dis[i], g[cur][i]);
        }
    }

    int res = 0;
    for (int i = 0; i <= n; ++ i) {
        if (dis[i] == inf) return -1;
        res += dis[i];
    }
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> g[0][i];
        g[i][0] = g[0][i];
    }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            cin >> g[i][j];
    
    cout << prim() << endl;
    return 0;
}