[C++/백준] 1238번: 파티

문제 링크

1238번: 파티

 

풀이

인접 리스트들에 대해 각 정점에서 목표 정점까지의 최단 거리를 구하는 다익스트라 문제
우선 순위 큐로 풀어야하나 싶은데 큐로 해도 풀리긴 함

1. 값을 입력 받으며 인접 리스트를 만들어줌
2. func에서 현재 정점인 cur에서 각 노드까지의 최단 거리를 구해준다.
   1. 거리를 갱신해줄 dist를 무한대로 만들어주고 시작 노드는 0
   2. 큐가 빌 때까지 반복하는데, 현재 노드인 curN에서 연결된 정점을 보며 각 노드까지 거리가 최소로 갱신될 때만 dist 갱신과 q에 추가해준다.
   3. 그렇게 현재 정점에서 각 노드까지의 최소 거리가 구해진다.
3. xdist는 집으로 각자 돌아갈 때인데, 한 번만 구해주면 각 노드까지의 최소 거리가 만들어진다.
4. xdist[i]와 cdist[i]를 더한 값이 가장 큰 것으로 구해준다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 100001
using namespace std;

vector<int> func(int cur, int n, vector<vector<pair<int, int>>>& arr)
{
    vector<int> dist(n + 1, INF);
    queue<int> q;
    dist[cur] = 0;
    q.push(cur);

    while (!q.empty())
    {
        int curN = q.front();
        q.pop();
        for (int i = 0; i < arr[curN].size(); i++)
        {
            int nextN = arr[curN][i].first;
            int nextT = arr[curN][i].second;
            if (dist[nextN] > dist[curN] + nextT)
            {
                dist[nextN] = dist[curN] + nextT;
                q.push(nextN);
            }
        }
    }

    return dist;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, x;
    cin >> n >> m >> x;

    vector<vector<pair<int, int>>> arr(n + 1);
    for (int i = 0; i < m; i++)
    {
        int stt, end, t;
        cin >> stt >> end >> t;
        arr[stt].push_back({ end,t });
    }

    int answer = -1;

    vector<int> xdist = func(x, n, arr); // x에서 모든 정점들에 대한 최단 거리

    for (int i = 1; i <= n; i++)
    {
        vector<int> cdist = func(i, n, arr);
        answer = max(answer, cdist[x] + xdist[i]);
    }

    cout << answer;
}