智灵普及加综合题3 - 信友队
求思路 @肖奕宇
输入(存边就行)
然后将边按边权从小到大排序
对于每条边i
找他后面的边
用并查集记录两点的祖父关系
如果1和n同组先
则记录答案后break掉
最后输出
示例核心代码:
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
p[j] = j;
}
for (int j = i; j <= m; j++) {
p[find(a[j].x)] = find(a[j].y);
if (find(1) == find(n)) {
ans = min(ans, abs(a[i].z - a[j].z));
break;
}
}
}
3 个赞
WA了可以帮调
2 个赞
OK