文章

2

粉丝

36

获赞

2

访问

853

头像
牛客能通过全部用例,N诺只有80%
P1341 浙江大学机试题
发布于2024年6月26日 22:36
阅读数 380

牛客能通过全部用例,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;
...
登录查看完整内容


登录后发布评论

1 条评论
snake VIP
2024年6月26日 22:56

数据更强吧,考虑有重边和自环的情况

mpt初始化无穷大,自身到自身是0

赞(0)