2坑，3次WA。
1.判断重边取小。2.自边舍去。
（个人因为vis数组忘记初始化，WA了3次，晕死！！）
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec int 11 using namespace std; 12 13 const int V = 1005; 14 const typec inf = 0xffff; 15 int vis[V]; 16 typec lowc[V]; 17 int Map[V][V]; 18 19 typec prim (typec cost[][V], int n) { 20 int i, j, p; 21 typec minc, res = 0; 22 memset(vis, 0, sizeof(vis)); 23 vis[0] = 1; 24 for (i = 1; i < n; ++ i) lowc[i] = cost[0][i]; 25 for (i = 1; i < n; ++ i) { 26 minc = inf; p = -1; 27 for (j = 0 ; j < n; ++ j) { 28 if (0 == vis[j] && minc > lowc[j]) { 29 minc = lowc[j]; p = j; 30 } 31 } 32 if (inf == minc) return -1; 33 res += minc; vis[p] = 1; 34 for (j = 0 ; j < n; ++ j) { 35 if (0 == vis[j] && lowc[j] > cost[p][j]) { 36 lowc[j] = cost[p][j]; 37 } 38 } 39 } 40 return res; 41 } 42 43 int main () { 44 int n, road_n; 45 int cur = 0; 46 while (cin >> n >> road_n) { 47 /*if (cur ++ != 0) { 48 cout << endl; 49 }*/ 50 for (int i = 0 ; i < n; ++ i) { 51 for (int j = 0 ; j < n; ++ j) { 52 if (i == j) Map[i][j] = 0; 53 else { 54 Map[i][j] = inf; 55 } 56 } 57 } 58 59 for (int i = 0 ; i < road_n; ++ i) { 60 int x, y, c; 61 scanf("%d%d%d", &x, &y, &c); 62 if (x == y) { 63 continue; 64 } 65 Map[x][y] = Map[y][x] = min(Map[x][y], c); 66 } 67 68 int ans = prim (Map, n); 69 70 if (ans == -1) { 71 cout << "impossible" << endl << endl; 72 } else { 73 cout << ans << endl << endl; 74 } 75 } 76 return 0; 77 }