求助
查看原帖
求助
400333
qzilr楼主2022/6/19 18:06

第6个点WA了,不知道什么原因,求助

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
	int v, w, nxt;
}t[maxn];
int head[maxn], tot = 0, vis[maxn], id = 1;
long long d[maxn], coy[maxn], ans = 0, minn = 0;
void add (int u, int v, int w) {
	t[++ tot] = (node){v, w, head[u]};
	head[u] = tot;
}
void dfs (int u) {
    vis[u] = 1;
	for (int i = head[u]; i; i = t[i].nxt ) {
		int v = t[i].v ;
        if (vis[v]) continue;
        vis[v] = 1;
		d[v] = d[u] + t[i].w ;
		if (d[id] < d[v])	id = v;
		dfs (v);
	}
}
int main () {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++) {
		int u, v, t;
		scanf("%d%d%d", &u, &v, &t);
		add (u, v, t);
		add (v, u, t);
	}
	dfs (1);
	memset (d, 0, sizeof(d));
    memset (vis, 0, sizeof(vis));
	dfs (id);
	ans += d[id];
	for (int i = 1; i <= n; i ++)	coy[i] = d[i];
    memset (d, 0, sizeof(d));
    memset (vis, 0, sizeof(vis));
	dfs (id);
	for (int i = 1; i <= n; i ++) {
		if (minn < min (d[i], coy[i]))	minn = min (d[i], coy[i]);
	}
	printf("%lld", ans + minn);
	return 0;
}
2022/6/19 18:06
加载中...