rt,代码如下,RE部分已标出
const int N = 2e6 + 10;
struct Edge {
int u, v, val;
} g[N];
struct Point {
int id, val;
};
int n = read(), m = read(), h[N / 10], fa[N / 10], cnt, ans, en;
inline bool cmp (Edge a, Edge b) {
if (h[a.v] != h[b.v]) return h[a.v] > h[b.v];
return a.val < b.val;
}
inline int find (int x) {
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
inline void merge (int x, int y) {
int fx = find(x), fy = find(y);
fa[fy] = fx;
}
vector <Point> e[N / 10];
int q[N / 10], l, r;
signed main()
{
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i)
h[i] = read();
for (int i = 1; i <= m; ++i) {
int u = read(), v = read(), val = read();
if (h[u] >= h[v]) e[u].push_back({v, val});
if (h[u] <= h[v]) e[v].push_back({u, val});
}
l = 1;
r = 2;
q[l] = 1;
///RE///
while (l != r) {
int x = q[l]; l ++;
for (Point y : e[x]) {
en ++;
g[en].u = x;
g[en].v = y.id;
g[en].val = y.val;
q[++ r] = y.id;
cnt ++;
}
}
///RE///
sort(g + 1, g + en + 1, cmp);
for (int i = 1; i <= en; ++i) {
int u = g[i].u, v = g[i].v, val = g[i].val;
if (find(u) != find(v)) {
merge(u, v);
ans += val;
}
}
out(cnt, 's');
out(ans, 'l');
return 0;
}
话说为什么手动模拟队列还会RE啊