글 읽기 - [C++] 프림 알고리즘 방식 코드 어느 부분이 잘못 되었는지 모르겠습니다ㅠ

hippo 3년 전 0

4 5

1 2 1

1 3 5

2 3 2

2 4 5

3 4 3

4 5

2 4 5

2 3 2

1 3 3

3 4 5

1 2 1

등 테스트 데이터를 추가해서 돌렸는데 값이 제대로 나옵니다.

하지만 제출하면 틀렸다고 나옵니다.

잘못된 부분을 고민해봤지만 제 머리론 찾지 못해서 질문합니다.

어디가 잘못되었나요ㅜㅠ..?

#include<iostream>
#include<queue>
#include<vector>
#include<limits>
#define MAX 10000
#define INF std::numeric_limits<int>::max()

using namespace std;

struct Node{
    int num;
    int key;
    int pi;
    Node(int num):num(num), key(INF), pi(-1){}
};
struct Edge{
    int to;
    int cost;
    Edge(int to, int cost):to(to), cost(cost){}
};


bool visited[MAX]={false};
vector<Edge*> edge[MAX];
int n,m;

int MST_Prim(){
    auto cmp = [](Node *a, Node *b){return a->key > b->key;};
    priority_queue<Node*, vector<Node*>, decltype(cmp)> q(cmp);
    Node *vertex[MAX] = {nullptr};
    int sum=0, nNode=0;

    for(int i=1; i<=n; i++) vertex[i] = new Node(i);

    vertex[1]->key = 0;
    q.push(vertex[1]);

    while(!q.empty()){
        Node *target = q.top();
        q.pop();

        if(nNode==n)
            break;

        if(visited[target->num])
            continue;
        //cout<<"("<<target->pi<<"-"<<target->num<<") "<<target->key<<endl;
        sum+=target->key;
        nNode++;
        visited[target->num]=true;

        for(int i=0; i<int(edge[target->num].size()); i++){
            if(!visited[edge[target->num][i]->to]){
                if(edge[target->num][i]->cost < vertex[edge[target->num][i]->to]->key) {
                    vertex[edge[target->num][i]->to]->key = edge[target->num][i]->cost;
                    vertex[edge[target->num][i]->to]->pi = target->num;
                    q.push(vertex[edge[target->num][i]->to]);
                }
            }
        }
    }
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int e1, e2, cost;
        cin>>e1>>e2>>cost;
        edge[e1].push_back(new Edge(e2, cost));
        edge[e2].push_back(new Edge(e1, cost));
    }
    cout<<MST_Prim()<<endl;

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 프림 알고리즘 방식 코드 어느 부분이 잘못 되었는지 모르겠습니다ㅠ

hippo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말