[백준 18126번] 너구리 구구 (C++)

문제링크 : https://www.acmicpc.net/problem/18126

18126번: 너구리 구구

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MAX = 10000000001*5000; //최대값 + 1

int N, A, B; 
ll C, result;
vector<pair<int, ll>>v[5001];
ll dist[5001];

void bfs()
{
    dist[1]=0; //시작점
    queue<pair<int, ll>> q;
    q.push({1, 0});

    while(!q.empty())
    {
        auto[cur, cost] = q.front(); //현재위치, 현재거리값
        q.pop();

        for(int i=0; i<v[cur].size(); i++)
        {
            auto [next, ncost] = v[cur][i]; //다음위치, 다음거리값
            if(dist[next] > cost + ncost)
            {
                dist[next] = cost + ncost;
                q.push({next, dist[next]});
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N-1; i++) 
    {
        cin >> A >> B >> C;
        v[A].push_back({B, C}); //양방향
        v[B].push_back({A, C});
    }

    for(int i=1; i<=N; i++) dist[i] = MAX;
  
    bfs();
    for(int i=1; i<=N; i++) result = max(result, dist[i]); //최대거리
    cout << result;
    return 0;
}

 

먼저 양방향 그래프이므로 각 방향에 대한 값을 연결해준다.

그리고 거리를 저장해야하는데, 이를 우선 MAX 값으로 초기화 해준다.

이때 MAX값은 해당 문제에서 나올 수 있는 최대값인 1000000000*5000을 이용하여 설정했다. (N*C)

 

이후 bfs를 통해 연결된 값을 확인하며, 이때 현재 비용과 다음 비용을 합쳐 dist 배열에 갱신한다.

이후 dist배열에서 가장 큰 값을 출력하면 된다.

 

해당 문제에서 주의해야할 것은 값의 범위가 상당히 크다는 것이다.

따라서 cost와 관련된 값들에 longlong을 사용해주어야 한다.