我的思路+ 理解

刚开始我以为只能建立一个站， 所以以为最小生成树+ 最小的v[i]就行了， 结果wa了， 因为可能建立多个发电站

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
const ll INF = 0x3f3f3f3f;
ll g[400][400];
ll n;
ll v[maxn], dis[maxn];
bool st[maxn];

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

    ll res = 0;
    for(int i = 1; i <= n+1; i ++)
    {
        ll t = -1;
        for(int j = 0; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dis[j] < dis[t]))
            {
                t = j;
            }
        }
        res += dis[t];
        st[t] = true;
        for(int j = 1; j <= n; j ++)
            dis[j] = min(dis[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> g[i][j];

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