31分代码，还有最后一个测试点没过
1 #include<iostream> 2 #include <map> 3 using namespace std; 4 #define infinite 100000000 5 int main() 6 { 7 int built[101][101]; 8 long long int cost[101][101];//两个村庄之间道路费用 9 long long int low[101];//最小生成树到村庄的最短距离 10 int N; 11 cin >> N; 12 for (int i = 1; i <= N; i++)low[i] = infinite; 13 for (int i = 1; i <= N; i++) 14 for (int j = 1; j <= N; j++) 15 cost[i][j] = cost[j][i] = infinite; 16 for (int i = 0; i < N * (N - 1) / 2; i++) 17 { 18 int a, b; 19 cin >> a >> b; 20 cin >> cost[a][b]; 21 cost[b][a] = cost[a][b]; 22 cin >> built[a][b]; 23 built[b][a] = built[a][b]; 24 if (built[a][b] == 1) 25 { 26 low[a] = low[b] = 0; 27 for (int i = 1; i <= N; i++) 28 { 29 if (cost[a][i] < low[i]) 30 low[i] = cost[a][i]; 31 if (cost[b][i] < low[i]) 32 low[i] = cost[b][i]; 33 } 34 } 35 } 36 low[1] = 0; 37 for (int i = 1; i <= N; i++) 38 { 39 if(cost[1][i] < low[i]) 40 low[i] = cost[1][i]; 41 } 42 long long int sum = 0; 43 for (int c = 0; c < N-1; c++)//prim算法 44 { 45 int min = infinite; 46 int k = -1; 47 for (int i = 1; i <= N; i++) 48 { 49 if (low[i] < min && low[i] != 0) 50 { 51 min = low[i]; 52 k = i; 53 } 54 } 55 if (k == -1)break; 56 sum += min; 57 low[k] = 0; 58 for (int x = 1; x <= N; x++) 59 { 60 if (cost[k][x] < low[x] && low[x] != 0) 61 { 62 low[x] = cost[k][x]; 63 } 64 } 65 } 66 cout << sum; 67 return 0; 68 }