传送门
Problem Description
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
Input
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，
其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
Output
对于每组测试数据，输出1个整数Ans。
表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
Sample Input
5
0 1005 6963 392 1182
1005 0 1599 4213 1451
6963 1599 0 9780 2789
392 4213 9780 0 5236
1182 1451 2789 5236 0
Sample Output
4178
Solution
最小生成树Prim算法
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
//Prim算法
const int maxn = 1005;
//vis用来记录某个点是否被访问过，d用来记录无效集连接到有效集的最小值
int n,mat[maxn][maxn],vis[maxn],d[maxn];
int end,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mat[i][j]);
memset(d,0x3f3f3f3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[1]=0;
ans=0;
for(int i=1;i<=n;i++){
end=-1;
for(int j=1;j<=n;j++){
//如果该点没有被访问过并且（end是第一个元素或者j到有效集的距离小于最小的距离，则更新最小下标)
if(!vis[j]&&(end==-1||d[end]>d[j]))
end=j;
}
ans += d[end];
vis[end]=1;
//更新无效集中每个点到有效集的最小值
for(int j=1;j<=n;j++){
if(!vis[j]&&d[j]>mat[end][j])
d[j] = mat[end][j];
}
}
printf("%d\n",ans);
return 0;
}