题意：存在许多点和点与点之间的路径，路径长度不一，点到点之间可能存在多条路径。挑选部分路径使得所有点连通且总路径长度最小。
分析：连通+路径长度最小 = 最小生成树。
Prim算法适用于稠密图, Kruskal适用于稀疏图
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 110, INF = 0x3f3f3f3f;
int n, m, g[N][N], f[N];
struct T {
int u, v, w;
T(int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
bool operator<(const T& r) const { return w < r.w; }
} t[N * N];
int dis[N];
bool st[N];
int prim() {
memset(dis, 0x3f, sizeof(dis));
memset(st, 0, sizeof(st));
int ans = 0;
for (int i = 1; i <= n; i++) {
int u = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (u == -1 || dis[j] < dis[u]))
u = j;
if (i > 1 && dis[u] == INF) return -1;
if (i > 1) ans += dis[u];
for (int j = 1; j <= n; j++)
if (dis[j] > g[u][j]) dis[j] = g[u][j];
st[u] = 1;
}
return ans;
}
int find(int u) {
return u == f[u] ? u : f[u] = find(f[u]);
}
int kruskal() {
sort(t + 1, t + 1 + m);
for (int i = 0; i <= n; i++) f[i] = i;
int ans = 0, cnt = 0;
for (int i = 1; i <= m; i++) {
int fu = find(t[i].u), fv = find(t[i].v);
if (fu != fv) f[fu] = fv, ans += t[i].w, cnt++;
if (cnt == n - 1) break;
}
return ans;
}
int main() {
while (~scanf("%d%d", &n, &m) && n) {
memset(g, 0x3f, sizeof(g));
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
g[u][v] = g[v][u] = min(g[u][v], w);
t[i] = T(u, v, w);
}
printf("%d\n", prim());
// printf("%d\n", kruskal());
}
return 0;
}