글 읽기 - 크루스칼 문제 질문입니다~

xkth342 7년 전 0

6% 까지 가다가 틀렸다고하네요 왜 틀린지 모르겠어요 반레가되는 테스트케이스도 알려주시면 감사하겠습니다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n,num,a,b,c;
int sum =0;
vector<int>visited;
vector<int> arr[1001];
typedef pair<int,pair<int,int>> PII;
priority_queue<PII,vector<PII>,greater<PII>> PQ;
void input(){
    scanf("%d%d",&n,&num);
    for(int i=0; i< num; i++)                                 /// 우선순위큐로 노드 및 가중치 입력
        scanf("%d%d%d",&a,&b,&c), PQ.push({c,{a-1,b-1}});
}
int beg,ed,val;

bool cycle;
void mst(){
    while(!PQ.empty()){ cycle = false; visited.assign(n,0);   // 우선순위큐 순회
        beg = PQ.top().second.first; ed = PQ.top().second.second; val = PQ.top().first;   
        PQ.pop();

        queue<int> Q; // 사이클확인을 위한 탐색 컨테이너
        Q.push(beg);
        while(!Q.empty()){ 

            int wow = Q.front();
            Q.pop();
            for(vector<int> :: iterator it = arr[wow].begin(); it != arr[wow].end(); it ++){
                if(!visited[*it]) {
                    visited[*it] = true;
                    if (*it == ed) {                  //// 사이클유무 확인
                        cycle = true;    
                        break;
                    }
                    Q.push(*it);
                }
            }
        }
        if(cycle == false) {sum +=val;arr[beg].push_back(ed); arr[ed].push_back(beg);} 
                       // 사이클이없으면 연결하고 가중치 추가


    }

}

void output(){
    printf("%d",sum);
}
int main() {
    input();
    mst();
    output();
}

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

문제

문제

출처

ICPC

크루스칼 문제 질문입니다~

xkth342 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말