Prim只过了最后三点 第一测试点输出980

P3366 【模板】最小生成树

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谢谢


|