Kotori_Kawaii @ 2024-12-16 10:51:11
求大佬指点T T
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 1000000007
int N,M;
bool vis[5005]={false};
vector<int>dist(5005,MAXN);
int sum=0;
void Prim(vector<vector<int>>&graph,int pos){
dist[pos]=0;
vis[pos]=true;
for(int i=1;i<N;i++)dist[i]=min(dist[i],graph[pos][i]);
for(int i=1;i<N;i++){
int cur=-1;
for(int j=0;j<N;j++){
if(!vis[j]&&(cur==-1||dist[j]<dist[cur]))
cur=j;
}
if(dist[cur]==MAXN){sum=MAXN;return;}
vis[cur]=true;
sum+=dist[cur];
for(int i=0;i<N;i++){
if(!vis[i])dist[i]=min(dist[i],graph[cur][i]);
}
}
}
int main(){
cin >> N >> M;
vector<vector<int>>graph(N,vector<int>(N,MAXN));
int x,y,w;
for(int i=0;i<M;i++){
cin >> x >> y >> w;
graph[x-1][y-1]=graph[y-1][x-1]=w;
}
Prim(graph,0);
if(sum==MAXN)cout << "orz";
else cout << sum;
}
by Yuzu_Soft @ 2024-12-16 11:50:33
有重边
by Yuzu_Soft @ 2024-12-16 11:51:27
@Kotori_Kawaii
by Kotori_Kawaii @ 2024-12-16 22:11:44
@Yuzu_Soft okok谢谢