@[julihui325](/user/553577) 根据亲测，最后一个点构不成最小生成树的原因是遍历完所有的边后没有 $n - 1$ 条。
by jimmy0926 @ 2024-08-02 08:35:07
@[julihui325](/user/553577) 下载数据得：
```plain
input:
5 6
1 2 3
2 3 4
3 1 4
4 5 6
5 4 6
1 3 5
output:
orz
your output:
【啥也没有】
result:
process exited after xxx seconds with return value 3221225477
```
所以是 RE。
你谷的评测机对 RE 不敏感 ~~，我还有 RE 变 TLE 的经历~~ 。
by jimmy0926 @ 2024-08-02 08:46:24
~~谢谢关注~~
by jimmy0926 @ 2024-08-02 08:47:08
优先队列被取空了还在调用 ```q.top()```。
贴一份修改过的代码：
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read()
{
int x = 0;
short f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
struct edge {
int to, nxt, w;
} e[400010];
struct node {
int id, dist;
bool operator < (node x) const
{
return x.dist < dist;
}
};
int head[200010], tot;
void add(int u, int v, int w)
{
e[++tot].to = v;
e[tot].nxt = head[u];
e[tot].w = w;
head[u] = tot;
}
int n, m, dis[5010];
bool vis[5010];
priority_queue <node> q;
int main()
{
int u, v, w, cnt = 0, ans = 0;
n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read();
v = read();
w = read();
add(u, v, w);
add(v, u, w);
}
for (int i = 2; i <= n; i++) //关于你要从 1 开始赋初值
dis[i] = 0x3f3f3f3f;
q.push({1, 0});
while (!q.empty() && cnt < n) { //关于你用 || 操作符 且 cnt < n - 1
node t = q.top();
q.pop();
u = t.id;
if (vis[u])
continue;
vis[u] = 1;
ans += t.dist;
cnt++;
for (v = head[u]; v; v = e[v].nxt) {
if (e[v].w < dis[e[v].to]) {
dis[e[v].to] = e[v].w;
q.push({e[v].to, e[v].w});
}
}
}
if (cnt < n) //同上，居然 - 1
printf("orz");
else
printf("%d", ans);
return 0;
}
/*请注意细节*/
```
by jimmy0926 @ 2024-08-02 09:00:35
@[julihui325](/user/553577)
by jimmy0926 @ 2024-08-02 09:01:27
@[jimmy0926](/user/1162093) 已过，您真是个好人啊（感慨脸，大佬们都是人帅心善的
by julihui325 @ 2024-08-02 09:53:42
不用谢。
~~不知道该不该说，蒟蒻昨天才学最小生成树，正好不熟悉 Prim，想练手，又不(lan)想(de)敲，结果看到讨论区 _prim+优先队列，最后一个点t掉了，求调_，然后就没有然后了。。。~~
by jimmy0926 @ 2024-08-02 10:01:33