记录编号	554464	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.779 s
提交时间	2020-09-13 13:58:22	内存使用	15.25 MiB

#define INF 0x7f7f7f7f
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

int n;
int connections[2100][2100];
int minD[2100],parent[2100];
int ans;
bool inset[2100];
struct Searcher
{
    int num,dis;
    Searcher(int n = 0,int d = 0)
    {
        num = n,dis = d;
    }
    friend bool operator < (Searcher __x, Searcher __y)
    {
        return __x.dis > __y.dis;
    }
};
priority_queue<Searcher> schr;

int Prim(int start)
{
    memset(minD,0x7f,sizeof(minD));
    memset(parent,-1,sizeof(parent));
    minD[start] = 0;
    schr.push(Searcher(start,0));
    while(!schr.empty())
    {
        Searcher s = schr.top();
        schr.pop();
        if(!inset[s.num])
        {
            inset[s.num] = true;
            for(int i = 1;i <= n;i++)
            {
                if(!inset[i] && connections[s.num][i] < minD[i])
                {
                    parent[i] = s.num;
                    minD[i] = connections[s.num][i];
                    schr.push(Searcher(i,minD[i]));
                }
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        ans += minD[i];
    }
    return ans;
}

int main()
{
    freopen("mcst.in","r",stdin);
    freopen("mcst.out","w",stdout);
    cin >> n;
    int a;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> a;
            connections[i][j] = (a > -1 ? a : INF);
        }
    }
    cout << Prim(1);
    return 0;
}