题目：
提示：
Floyd最短路径算法实现(未测试)：
// // main.cpp // Alg_Floyd_playgame // // Created by wasdns on 16/11/19. // Copyright ? wasdns. All rights reserved. // #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <string.h> using namespace std; #define endless 1000000001; int Floydgh[5005][5005]; void Inigh(int n) { for (int i = 1; i <= n; i++) { Floydgh[i][i] = 0; for (int j = 1; j <= n; j++) { if (i != j) { Floydgh[i][j] = endless; } } } } void Creatgh(int n, int m) { Inigh(n); int i, u, v, w; for (i = 1; i <= m; i++) { cin >> u >> v >> w; Floydgh[u][v] = w; Floydgh[v][u] = w; } } void Alg_Floyd(int n) { int i, j, k; for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { int t = Floydgh[i][k] + Floydgh[k][j]; if (t < Floydgh[i][j]) { Floydgh[i][j] = t; Floydgh[j][i] = t; } } } } } int minjudge(int n) { int i, j; int minlen = endless; for (i = 1; i <= n; i++) { int cnt = 0; for (j = 1; j <= n; j++) { cnt += Floydgh[i][j]; } if (cnt < minlen) { minlen = cnt; } } return minlen; } int main() { int n, m; cin >> n >> m; Creatgh(n, m); Alg_Floyd(n); cout << minjudge(n) << endl; return 0; }
Prim生成树算法实现：
关于Prim算法，请参考我的另外一篇博客：hdoj-1233-还是畅通工程
//// main.cpp// Prim//// Created by wasdns on 16/11/24.// Copyright © wasdns. All rights reserved.//#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <string>#include <string.h>#define maxn 10000005;using namespace std;int Primgh[10000][10000];bool refer[10005];void Initial(int n, int m){int i, j;for (i = 1; i <= n; i++){refer[i] = false;for (j = 1; j <= n; j++){if (i == j) {Primgh[i][j] = 0;}else Primgh[i][j] = maxn;}}int u, v, w;for (i = 1; i <= m; i++){cin >> u >> v >> w;Primgh[u][v] = w;Primgh[v][u] = w;}}int Prim_Alg(int n, int m){Initial(n, m);int i, j, k;int ans = 0;refer[1] = true;//起点为1for (i = 1; i <= n-1; i++){int minlen = maxn;int rcd = 1;for (j = 1; j <= n; j++){if (!refer[j]) continue;int len1 = maxn;int rcd1 = 1;for (k = 1; k <= n; k++){if (!refer[k]){if (Primgh[j][k] < len1) {len1 = Primgh[j][k];rcd1 = k;}}}if (len1 < minlen) {minlen = len1;rcd = rcd1;}}//char check = 'A'+rcd-1;//cout << "rcd: " << check << endl;//cout << "minlen: " << minlen << endl;refer[rcd] = true;rcd = 1;ans += minlen;}return ans;}int main(){int n, m;cin >> n >> m;cout << Prim_Alg(n, m) << endl;return 0;}
测试样例：
/*eg1. Input:4 61 2 12 3 21 3 32 4 33 4 51 4 4Output:6eg2.Input:7 111 2 71 4 52 4 92 3 82 5 73 5 54 5 154 6 65 6 85 7 96 7 11Output:39*/
/11/24
