EXPLORACE

D题, 最小生成树模板题, 我的代码是用的二阶矩阵实现

/*
    prim 算法 - 二阶矩阵
*/
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e3+5;
const int inf = 0x3f3f3f3f;

int v[maxn][maxn];
int t;
int main() {
    cin >> t;
    for ( int x = 1; x <= t; x++)
    {
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if ( i == j ) v[i][j] = 0;
                else v[i][j] = inf;

        for ( int i = 1; i <= m; i++ ) {
            int a, b, w; cin >> a >> b >> w;
            v[a][b] = v[b][a] = w;
        }
        int ans[maxn], f[maxn];
        memset( f, 0, sizeof(f));

        for ( int i = 1; i <= n; i++ ) ans[i] = v[1][i];
        f[1] = 1;
        int cut = 1, j, sum = 0, minn;
        while ( cut < n) {
            minn = inf;
            for ( int i = 1; i <= n; i++ ) {
                if ( !f[i] && ans[i] < minn ) { minn = ans[i]; j = i; }
            }
            f[j] = 1; cut++; sum += ans[j];
            for ( int i = 1; i <= n; i++ ) {
                if ( !f[i] && ans[i] > v[j][i] ) ans[i] = v[j][i];
            }
        }
        cout << "Case #" << x << ": " << sum << " meters\n";
    }

}