题意：中文题目
思路：prim实现，因为有n*(n-1)/2条边，已经是饱和的边了，prim比较合适。
（1）将点1置为浏览过，点1可以到达其他每个点，所以用low[i]数组记录下目前到达i点的最小长度。
（2）在low数组中找出到达未浏览过的点且距离最近的，置为浏览过，记该店为pos。
（3）将pos点可达的所有点，来更新low数组，使得从已浏览过的点到达i点的距离最短为low[i]。
（4）返回到2继续执行，直到所有的点都浏览过。
在第2步时就可以顺便记录下最小路径长度了。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int v[N][N]; //权
int vis[N];
int low[N]; //到每个点的最小权 int prim(int n)//普里姆算法
{
memset(vis,,sizeof(vis));
int pos=vis[]=; //从点1开始
for(int i=; i<=n; i++) if(v[][i]>) low[i]=v[][i]; //目前到每个点的最小权
int ans=;
for(int i=; i<n; i++) //搞定另外n-1个点
{
int big=LONG_MAX;
for(int j=; j<=n; j++) //找权最小的边，及对应的点
{
if(!vis[j] && low[j]<big )
{
pos=j;
big=low[j];
}
}
ans+=big;//统计路径长
vis[pos]=;
for( int j=; j<=n; j++ )//更新到每个点的权值
if(!vis[j]) low[j]=min(low[j],v[pos][j]);
}
return ans;
} int main()
{
freopen("input.txt", "r", stdin);
int n, a, b, t;
while(scanf("%d",&n),n>)
{
int up=n*(n-)/;//超稠密图
for(int i=; i<up; i++)
{
scanf("%d%d%d",&a,&b,&t);
v[a][b]=v[b][a]=t;
}
printf("%d\n",prim(n));
}
return ;
}
AC代码