[백준][C++] 1238번: 파티 <203>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

1238번: 파티

생각의 흐름

이번 문제는 다익스트라를 딱 2번만 적용하면 되는 문제이다!!

 

문제는 처음에 각 정점에서 X로 가는 비용을 구하려면, 각 정점의 수만큼 다익스트라를 진행해줘야 된다는 점 이다.

다익스트라의 시간 복잡도는 O(ElogV) 인데, 총 정점의 수만큼 돌면 => E*ElogV => E의 최대 값이 1000 이라 했으니,

1000000 * logV 정도니 통과될거 같기는 하다... 하지만 느리다...

 

생각을 좀 바꿔보자!

애당초 처음에 각 정점에서 X까지의 최단거리를 구하기 위해 정점의 수만큼 다익스트라를 도는것이 잘못되었다.

 

처음 input을 받을때 다음과 반대 방향의 값도 받아준다.

vector<pair<int, int>> adj[2][MAX];

for (int i = 0; i < M; i++) {
    cin >> from >> to >> w;
    adj[0][from].push_back({w, to}); // 일반 단방향 경로
    adj[1][to].push_back({w, from});
}

인접리스트가 총 2개이다.

adj[0]은 정상적인 단방향 그래프

adj[1]은 비용은 동일하지만 방향이 뒤집힌 그래프 이다.

 

adj[1]을 사용하면 X로부터 각 정점의 최소거리를 구할수가 있게된다!

 

역방향으로 입력을 받으면 각 정점들에서 X로 가는 최단거리를 X->A 최단거리로 바꿔 생각할수가 있다.

다익스트라 한 번이면 각 정점들에서 X로 가는 최단거리를 구할수 있게 되는 것 이다!!

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 1001
#define INF 987654321

int N, M, X;
vector<pair<int, int>> adj[2][MAX];
int dist[2][MAX];

void Dijkstra(int level, int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    dist[level][start] = 0;

    while(!pq.empty()) {
        int nowCost = pq.top().first;
        int nowVertex = pq.top().second;
        pq.pop();

        if(nowCost > dist[level][nowVertex]) continue;
        
        for(auto e : adj[level][nowVertex]) {
            int nextCost = e.first;
            int nv = e.second;
            if(dist[level][nv] > nowCost + nextCost) {
                dist[level][nv] = nowCost + nextCost;
                pq.push({dist[level][nv], nv});
            }
        }
    }
}

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

    cin >> N >> M >> X;
    int from, to, w;
    for(int i = 0; i < M; i++){
        cin >> from >> to >> w;
        adj[0][from].push_back({w, to}); // 일반 단방향 경로
        adj[1][to].push_back({w, from});
    }

    for(int i = 0; i <= N; i++){
        dist[0][i] = INF;
        dist[1][i] = INF;
    }

    Dijkstra(1, X);
    Dijkstra(0, X);

    int res = -1;
    for(int i = 1; i <= N; i++){
        res = max(res, dist[0][i] + dist[1][i]);
    }
    cout << res;

    return 0;
}