백준 1238번 - 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

다익스트라 알고리즘을 작년 8월에 처음 공부한 뒤

 

지금까지 한 번도 복습하지 않았다..

 

당연히 그때도 어려웠지만 지금은 완전히 까먹은 상태여서 언젠간 해야지 하다가 결국 어제오늘 복습을 했다.

 

 

사실 bfs 문제를 풀다가 '가중치'가 일정하지 않은 문제를 만나서 급하게 다익스트라를 공부한거긴 함ㅎㅎ

 

 

어쨌든

 

문제를 분석해보면

 

도로들은 단방향으로 이루어져있고 -> 단방향 그래프

 

각각의 도로들을 지나가는데에는 T[i] 만큼의 시간이 걸린다 -> 각 간선의 가중치 = T[i]

 

이 정도로 요약하고 그래프 문제로 모델링하면 쉽게 풀린다.

 

 

해결 방법은 다음과 같다.

 

1. 모든 노드에서 다익스트라 알고리즘을 통해 X(도착지점)까지의 최단거리를 구한 뒤 따로 저장해 놓는다.

2. X에서 다익스트라 알고리즘을 통해 다른 모든 노드들까지의 최단 거리를 구한다.

3. 위에서 구한 두 가지 정보를 합해서 최댓값을 찾는다.

 

주의해야 할 점은

 

사용하는 check배열, dis배열의 초기화이다.

 

문제에서 모든 학생들은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다고 하였으므로

도착하지 못하는 예외 케이스는 따로 처리하지 않아도 된다.

 

코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
 
int n, m, x, u, v, w;
bool check[1004];
vector<pair<int, int>>g[1004];
int dis[1004];
 
void daijkstra(int start) {
    memset(dis, 127, sizeof(dis));
    memset(check, false, sizeof(check));
    dis[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> >pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int ver = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (check[ver] == true)continue;
        check[ver] = true;
        if (dis[ver] != wei)continue;
        for (int i = 0; i < g[ver].size(); i++) {
            int a = g[ver][i].second;
            int b = g[ver][i].first;
            if (dis[ver] + a < dis[b]) {
                dis[b] = dis[ver] + a;
                pq.push(make_pair(dis[b], b));
            }
        }
    }
}
 
int main() {
    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
    }
    vector<int>go(1004);
    for (int i = 1; i <= n; i++) {
        daijkstra(i);
        go[i] = dis[x];
    }
    daijkstra(x);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == x)continue;
        ans = max(ans, go[i] + dis[i]);
    }
    cout << ans << "\n";
}