문제 푼 날짜 : 2021-07-07

문제

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

접근 및 풀이

다익스트라를 이용하여 파티가 열리는 X 까지 최단거리를 구하고, 다시 X에서 각자 집까지 돌아오는 최단거리를 구하여 그 두 값의 합이 가장 큰 값을 출력해주었다.

코드

// 백준 1238번 : 파티
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 100000

int N, M, X;
vector<pair<int, int>> map[1001];

vector<int> dijkstra(int start) {
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int distance = -pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (dist[current] < distance) {
            continue;
        }
        for (int i = 0; i < map[current].size(); i++) {
            int next = map[current][i].first;
            int nextDistance = distance + map[current][i].second;

            if (nextDistance < dist[next]) {
                dist[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
    return dist;
}

int main() {
    int ans = -1;
    cin >> N >> M >> X;

    for (int i = 0; i < M; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        map[x].push_back(make_pair(y, w));
    }
    for (int i = 1; i <= N; i++) {
        vector<int> v1 = dijkstra(i);
        vector<int> v2 = dijkstra(X);
        
        ans = max(ans, v1[X] + v2[i]);
    }
    cout << ans << '\n';
    return 0;
}

결과

피드백

다익스트라 알고리즘에 점점 익숙해져가는 것 같다.
더 심화된 문제를 풀어봐야겠다.