文章
2
粉丝
36
获赞
2
访问
822
牛客能通过全部用例,N诺只有80%
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105;
int mpt[N][N];
int minDist[N];
int main(){
int n;
while(cin >> n){
memset(mpt, 0, sizeof(mpt));
memset(minDist, 0x3f, sizeof(minDist));
if(n == 0) break;
int e = n * (n - 1) / 2;
int sum = 0;
int from, to, fee;
while(e--){
cin >> from >> to >> fee;
mpt[from][to] = fee;
mpt[to][from] = fee;
}
for(int i = 1; i <= n; ++i) minDist[i] = mpt[1][i];
for(int i = 1; i < n; ++i){
int min = INF;
int next = -1;
for(int j = 1; j <= n; ++j){
if(minDist[j] != 0 && minDist[j] < min){
min = minDist[j];
next = j;
}
}
sum += min;
for(int j = 1; j <= n; ++j){
if(minDist[j] != 0 && mpt[next][j] < minDist[j]){
minDist[j] = mpt[next][j];
}
}
}
cout << sum << endl;
...
登录后发布评论
数据更强吧,考虑有重边和自环的情况
mpt初始化无穷大,自身到自身是0