[BOJ] 파티

학생들이 파티장을 갔다 오는데 걸리는 최소 시간 중 최대값을 구하는 문제이다.

문제풀이 전략
처음에는 플로이드-워셜 알고리즘으로 접근하려 했다.

각 지점에서 각 지점까지의 최단 거리를 모두 구한 후 n->x, x->n 값의 합 중 최소값만 구하면 될 것이라 생각했다.

하지만 플로이드-워셜 알고리즘을 쓸 경우 O(n^3)의 시간복잡도가 들게 되는데, 문제 조건상 n이 1000까지 이므로 시간초과가 날 것으로 예상되었다.

문제 조건에서 그래프는 단방향 그래프라고 되어 있다.

또한 모든 학생은 X로 갈수 있고, X에서 집으로 돌아올 수 있다.

따라서 돌아오는 부분은 X에서 다익스트라 알고리즘을 적용하고, 가는 부분은 방향을 반대 방향으로 하여 X에서 다익스트라 알고리즘을 적용하면 된다.

정리하자면

1. 그래프를 만든다.(정방향, 역방향)
2. 두 그래프를 X를 시작으로 다익스트라 알고리즘을 적용한다.
3. 두 거리의 합의 최대값을 구한다.

주의할 점

코드를 짜고 나서 계속 틀렸습니다가 나왔다.

다익스트라 알고리즘을 적용할 때 최대 길이를 101로 해 놔서 그랬다.

101이 n개 있을 때 최대가 되는데, 이부분을 생각안하고 그냥 최대를 101로 해서 누적된 거리가 101보다 클때 멈춰서 생긴 문제였다.

앞으로 조건을 좀 더 잘 생각해야 겠다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> dijkstra(vector<vector<pair<int,int>>> g, int x, int n){
    vector<int> dis(n+1, -1);

    dis[x] = 0;
    priority_queue<pair<int,int>> q; // 거리, 현재지점
    q.push(make_pair(0,x));

    while(!q.empty()){
        int d = -q.top().first;
        int s = q.top().second;
        q.pop();
        if(dis[s] < d)
            continue;
        for(int i=0;i<g[s].size();i++){
            int to = g[s][i].first;
            int dist = g[s][i].second;
            if(dis[to] != -1 && dis[to] <= d + dist)
                continue;
            dis[to] = d + dist;
            q.push(make_pair(-dis[to], to));
        }
    }

    vector<int> ret;
    for(int i=0;i<=n;i++){
        ret.push_back(dis[i]);
    }
    return ret;
}

int main() {
    int n,m,x;

    cin >> n >> m >> x;

    vector<vector<pair<int,int>>> v(n+1);
    vector<vector<pair<int,int>>> rv(n+1);

    for(int i=0;i<m;i++){
        int s,e, t;
        cin >> s >> e >> t;
        v[s].push_back(make_pair(e,t));
        rv[e].push_back(make_pair(s,t));
    }

    vector<int> vv = dijkstra(v, x, n);
    vector<int> rvv = dijkstra(rv, x, n);

    int ans = -1;
    for(int i=1;i<vv.size();i++){
        ans = max(ans, vv[i]+rvv[i]);
    }
    cout << ans << "\n";
    return 0;
}

출처
https://www.acmicpc.net/problem/1238