最小生成树maylb代码

以下是Prim算法实现的最小生成树的代码，时间复杂度为O(n^2)：

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
int g[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];

int prim()
{
    memset(vis, false, sizeof(vis));
    memset(dist, INF, sizeof(dist));
    dist[1] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == 0 || dist[j] < dist[u]))
                u = j;
        vis[u] = true;
        ans += dist[u];
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] < dist[v])
                dist[v] = g[u][v];
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, INF, sizeof(g));
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = w;
    }
    printf("%d\n", prim());
    return 0;
}