[training Day1] spy dispatch

Spy dispatch

---

Their thinking

Connect all nodes with the least cost , use Minimum spanning tree .
In order to deal with the cost of participating in the task , We associate each node with “ The root node ” Connected to a , The boundary right is $M_k$.

code

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,ans,s;
int v[1010];
int minn[1010];
int a[1010][1010];

int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
    
		int t;
		scanf("%d",&t);
		minn[i]=t;
		a[i][n+1]=a[n+1][i]=t;
	}
	v[++n]=1;
	for(int i=1;i<n;i++)
	{
    
		int t,mi=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
			if(!v[j]&&mi>minn[j])
				t=j,mi=minn[j];
		v[t]=1;
		ans+=mi;
		for(int j=1;j<=n;j++)
			minn[j]=min(minn[j],a[t][j]);
	}
	cout<<ans<<endl;
}