其余点AC
by lighthouse @ 2021-11-14 11:15:46
借楼问一下，这道题我30分，不知道哪错了
code：
[https://www.luogu.com.cn/paste/pxht2n4v](https://www.luogu.com.cn/paste/pxht2n4v)
by yangyuanxi44 @ 2021-11-14 11:24:24
@[yangyuanxi44](/user/450893) 最小生成树一般用prim或克鲁斯卡尔求，您这，最后得到的不一定是一棵树吧
by Mr_ll @ 2021-11-14 11:46:37
@[Mr_ll](/user/365532) 帮@[yangyuanxi44](/user/450893) 回复，他说他用的prim
by Liweiang @ 2021-11-14 12:50:13
```cpp
#include <bits/stdc++.h>
#define INF 10001
using namespace std;
int dis[5005];
int a[5005][5005];
bool vis[5005];
int main(){
int n, m, mst = 0, tot = 0;
cin >> n >> m;
memset(a, 0x7f, sizeof(a));
for(int i = 1;i <= n;i++){
dis[i] = INF;
}
for(int i = 1;i <= m;i++){
int x, y, z;
cin >> x >> y >> z;
a[x][y] = min(a[x][y], z);
a[y][x] = min(a[y][x], z);
}
dis[1] = 0;
for(int i = 1;i <= n;i++){
int minn = INF, t = 1;
for(int j = 1;j <= n;j++){
if(vis[j] == 0 && dis[j] < minn){
minn = dis[i];//注意，就是这的，j敲成了i
t = j;
}
}
if(vis[t] == 1)
continue;
vis[t] = 1;
for(int j = 1;j <= n;j++){
if(vis[j] == 0 && a[t][j] < dis[j]){
dis[j] = a[t][j];
}
}
}
for(int i = 1;i <= n;i++){
if(dis[i] == 10001) tot++;
else mst += dis[i];
}
if(tot != 0) cout << "orz";
else cout << mst;
return 0;
}
```
by Mr_ll @ 2021-11-14 14:47:05
@[lighthouse](/user/218180)
by Mr_ll @ 2021-11-14 14:48:46
@[yangyuanxi44](/user/450893) ,您那个排序挺高级的鸭，从大到小（雾），emm，vector我不太清楚，我觉得可能是先按编号排了点，其实应该是边权优先
代码我改了改，还没交（可能会TLE）
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> p;
int dis[1000005],head[1000005],n,m,cnt;
bool vis[1000005];
priority_queue<pair<int,int> >Q;
struct EDGE{
int to,w,next;
}edge[1000005];
void init(){
for(int i=0 ; i<=n ; i++)
dis[i]=0x7fffffffffffffff;
}
void add(int u,int v,int w){
cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
signed main(){
cin>>n>>m;
init();
for(int i=1 ; i<=m ; i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
Q.push(make_pair(0,1));
dis[1]=0;
int e=0,ans=0;
while(!Q.empty()&&e<n){
int root=Q.top().second,dis1=-Q.top().first;
Q.pop();
if(vis[root])
continue;
vis[root]=true;
ans+=dis1;
e++;
for(int i=head[root] ; i!=0 ; i=edge[i].next){
if(edge[i].w<dis[edge[i].to]){
dis[edge[i].to]=edge[i].w;
Q.push(make_pair(-dis[edge[i].to],edge[i].to));
}
}
}
if(e==n)
cout<<ans;
else
cout<<"orz";
return 0;
}
```
by Mr_ll @ 2021-11-14 15:04:47
@[Mr_ll](/user/365532) 谢谢大佬
by yangyuanxi44 @ 2021-11-14 15:26:42
@[Mr_ll](/user/365532) 谢谢大佬，过了，应该是优先队列小根堆弄错了，下次还是重载运算符吧,多谢多谢
by yangyuanxi44 @ 2021-11-14 15:32:15
@[yangyuanxi44](/user/450893) 不用谢，正好又学了一下prim，（其实从未用过prim）
by Mr_ll @ 2021-11-14 15:34:25