Prim只过了最后三点 第一测试点输出980
查看原帖
Prim只过了最后三点 第一测试点输出980
1053560
Kotori_Kawaii楼主2024/12/16 10:51

求大佬指点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;
}
2024/12/16 10:51
加载中...