백준[1238] - 파티

문제

백준 1238 문제 보기

접근 방법

다익스트라 알고리즘을 사용하되 다시 각자의 마을로 복귀해야 하므로 다익스트라 알고리즘을 한번 더 사용한다.

dis_go 배열에는 갈때의 비용을 저장하고 dis_come 배열에는 다시 돌아올때의 비용을 저장한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;

int N, M, X, ans = -1, dis_go[1001], dis_come[1001];
vector<vector<pair<int, int>>> graph;
priority_queue<pair<int, int>> pq;

int main() {
    // 학생, 도로 숫자, 도착 마을
    cin >> N >> M >> X;

    // 마을 수 만큼 그래프를 증가
    graph.resize(M+1);

    for(int i = 0; i < M; i ++) {
        int from, to, time;
        cin >> from >> to >> time;
        // 그래프를 그림
        graph[from].push_back({to, time});
    }

    // 모든 마을에서 도착지점으로 가야하므로 반복문 사용
    for(int i = 1; i <= N; i ++) {
        // 출발지 설정
        int source = i;
        // 우선순위 큐를 초기화(나에게 오는 비용은 0)
        pq.push({0, source});
        // 모든 비용을 -1로 처리
        memset(dis_go, -1, sizeof(dis_go));

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

            // 방문한 적이 있다면 무시
            if(dis_go[here] != -1) {
                continue;
            }

            // 해당 마을까지의 비용을 저장
            dis_go[here] = cost;

            // 현재 마을로 부터 연결된 지점을 탐색
            for(int n = 0; n < graph[here].size(); n ++) {
                int next = graph[here][n].first;
                int n_cost = -graph[here][n].second - cost;

                // 방문한 적이 있다면 무시
                if(dis_go[next] != -1) {
                    continue;
                }

                // 새로운 마을이라면 우선 순위큐에 삽입
                pq.push({n_cost, next});
            }
        }

        // 원래 마을로 복귀해야 하므로 도착지점을 출발지점으로 설정
        pq.push({0, X});
        memset(dis_come, -1, sizeof(dis_come));

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

            if(dis_come[here] != -1) {
                continue;
            }

            dis_come[here] = cost;

            for(int n = 0; n < graph[here].size(); n ++) {
                int next = graph[here][n].first;
                int n_cost = -graph[here][n].second - cost;

                if(dis_come[next] != -1) {
                    continue;
                }

                pq.push({n_cost, next});
            }
        }

        ans = max(ans, dis_go[X] + dis_come[source]);
    }

    cout << ans;
}