글 읽기 - 100%에서 틀렸다고 나옵니다. 트리의 지름 문제...

msmsms0804 3년 전 0

우선순위 큐를 사용한 다익스트라로 트리의 지름을 구하였습니다. 예제 샘플은 맞게 나오는데 답이 100%에서 틀렸다고 나옵니다.

도대체 어디서 틀린 것일 까요???

제발 도와주세요!!!

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
typedef long long ll;

const int INF = 1e9;
int n;
vector<pii> v[100001];

vector<int> dijk(int start){
    vector<int> dist(n+1,INF);
    dist[0] = 0;
    dist[start] = 0;
    priority_queue<pii> pq;
    pq.push({0,start});
    while(!pq.empty()){
        int cur = pq.top().ss;
        int cur_distance = -pq.top().ff;
        pq.pop();
        if(cur_distance > dist[cur])continue;
        for(auto & i : v[cur])
            if(i.ss + cur_distance < dist[i.ff]){
                dist[i.ff] = i.ss + cur_distance;
                pq.push({-(i.ss + cur_distance),i.ff});
            }
    }
    return dist;
}
void solve(){
    cin>>n;
    int a,b,c;
    rep(i,n-1){
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    vector<int> dist = dijk(1);
    int index = max_element(dist.begin(),dist.end())-dist.begin();
    vector<int> dist1 = dijk(index);
    int index1 = *max_element(dist1.begin(),dist1.end());
    cout<<index1;
}
int main() {
    fast_io;
    solve();
}

sonjaewon 3년 전 1

n = 1 일때 이상하네요

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

문제

문제

출처

ICPC

100%에서 틀렸다고 나옵니다. 트리의 지름 문제...

msmsms0804 3년 전 0

sonjaewon 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말