ztyo_zysclown @ 2024-04-24 19:22:11
#include<bits/stdc++.h>
using namespace std;
const int N=520,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
memset(dist,0x3f,sizeof(dist));
int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j;
}
}//判断这个点对集合中的每一个点的边中最短的那一条
if(i&&dist[t]==INF) return INF;
if(i) res+=dist[t];//点不能是一
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],g[t][j]);
} //更新其他的点到集合的距离
st[t]=true;//入树
}
return res;
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof(g));
while(m--){
int u,v,m;
cin>>u>>v>>m;
g[u][v]=g[v][u]=min(g[u][v],m);
}
// for(int i=1;i<=n;i++){
// cout<<dist[i]<<" ";
// }
int t=prim();
if(t==INF){
cout<<"orz";
return 0;
}
cout<<t;
return 0;
}
by luuia @ 2024-04-24 19:34:09
N有5000不能用邻接表
by luuia @ 2024-04-24 19:35:15
改成链式前向星或者vector就对了
by elpsconr @ 2024-04-25 22:37:17
N改成5000就可以了,还有这个是邻接矩阵,不是邻接表,不要被楼上误导了.不过还是建议用链式前向星存图