글 읽기 - 기가 노드 구하는 게 잘못된 것 같은데, 한번 봐주시 수 있으실까요

skesswswkk 1년 전 0

80%에서 틀렸습니다가 뜹니다ㅠ

기가 노드 구하는 함수(fromRootToGiga)가 잘못된 것 같은데, 한번 봐주시 수 있으실까요?

#include <iostream>
#include <string> //find
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <climits>
#include <map>
#include <iomanip>
using namespace std;
const int M = 200000 + 5;

map<int, vector<pair<int, int>>> v;
int gigaNode = 0;
int gigaLen = 0;
int maxx = 0;

int visited[M];

bool sol(int x){
    int cnt = 0;
    for(int i = 0; i < v[x].size(); ++i){
        int now = v[x][i].first;
        if(visited[now] == 0) cnt++;
    }
    
    if(cnt >= 2) return true;
    else return false;
}

void fromRootToGiga(int x, int len){
//    cout << x << ", " << len << endl;
    //리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 된다.
    gigaNode = x;
    gigaLen = len;
    if(sol(x)){
        return;
    }
    else {
        for(int i = 0; i < v[x].size(); ++i){
            int now = v[x][i].first;
            
            if(!visited[now]){
                visited[now] = 1;
                fromRootToGiga(now, len+v[x][i].second);
            }
        }
    }
}

void maxFromGigaToLeaf(int x, int sum){
//    cout << x << ", sum :" << sum << endl;
    maxx = max(maxx, sum);
    
    for(int i = 0; i < v[x].size(); ++i){
        int now = v[x][i].first;
        if(!visited[now]){
            visited[now] = 1;
            
            maxFromGigaToLeaf(now, sum + v[x][i].second);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, r;
    cin >> n >> r;
    
    if(n == 1 && r == 1){
        cout << "0 0\n";
        return 0;
    }
    
    for(int i = 0; i < n-1; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        
        v[a].push_back({b, c});
        v[b].push_back({a, c});

    }
    
//    //output
//    for(int i = 1; i <= n; ++i){
//        cout << "*" << i << "::";
//        for(int j = 0; j < v[i].size(); ++j){
//            cout << v[i][j].first << ", ";
//        }cout << endl;
//    }
    
    gigaNode = r;
    gigaLen = 0;
    visited[r] = 1;
    fromRootToGiga(r, 0);

    //루트 노드가 동시에 기가 노드인 경우도 가능하다.
    if(v[r].size() == n-1){
        gigaNode = r;
        gigaLen = 0;
        memset(visited, 0, sizeof(visited));
    }
//    cout << ":::::::" << gigaNode << ", " << gigaLen << endl;

    maxFromGigaToLeaf(gigaNode, 0);
    
    cout << gigaLen << " " << maxx << endl;
}

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

문제

문제

출처

ICPC

기가 노드 구하는 게 잘못된 것 같은데, 한번 봐주시 수 있으실까요

skesswswkk 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말