求助,刚学Prim,最后一个特判点WA
查看原帖
求助,刚学Prim,最后一个特判点WA
352603
RainSpark楼主2022/6/25 14:21
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
#define ll long long
#define N 200005
#define INF 0x3f3f3f3f
using namespace std;
int head[N], num_edge;
int dis[N];
bool vis[N];
struct Edge {
	int nxt, to, dis;
} edge[2 * N];
void add(int from, int to, int dis) {
	num_edge++;
	edge[num_edge].nxt = head[from];
	edge[num_edge].to = to;
	edge[num_edge].dis = dis;
	head[from] = num_edge;
}
int cnt, n, m, tot, now = 1, ans;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w); //双向加边
		add(v, u, w);
	}
	for (int i = 2; i <= n; i++)
		dis[i] = INF;
	for (int i = head[1]; i; i = edge[i].nxt) {
		dis[edge[i].to] = min(dis[edge[i].to], edge[i].dis);
	}
	for (int i = 1; i <= n; i++) {
		if (tot >= n - 1)
			break;
		int minn = INF;
		vis[now] = 1;
		for (int j = 1; j <= n; j++) { //枚举每一个没有使用的点,找出最小值作为新边
			if (vis[j] == 0 && minn > dis[j]) {
				minn = dis[j];
				now = j;
			}
		}
		ans += minn;
		for (int j = head[now]; j; j = edge[j].nxt) { //枚举now的所有连边,更新dist数组
			int v = edge[j].to;
			if (dis[v] > edge[j].dis && vis[v] == 0) {
				dis[v] = edge[j].dis;
			}
		}
		tot++;
	}
	if (tot == n - 1)
		cout << ans << endl;
	else
		cout << "orz" << endl;
	return 0;
}


2022/6/25 14:21
加载中...