[백준 1238] 파티 C++

1238번: 파티

다익스트라

---

1. 문제 해결 아이디어

 

단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만

이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다.

 

A->X로 가는 최단거리를 구해보자.

 

정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다.

그래서 A->X로 가는 최단거리를 A의 개수만큼 반복문을 돌려서 다익스트라 알고리즘을 수행한 후 배열에 각각 저장했다.

resdist[A] = X로 가는 최단거리

 

이제 모든 정점에서 X로 가는 최단거리를 구했다.

 

X에서 다른 정점으로 가는 최단거리들을 구하는건 일반적인 다익스트라 알고리즘을 한 번만 수행하면 된다.

 

---

그런데 정점의 개수가 100,000개가 되면 위 풀이를 쓸 수가 없다

 

정점들의 정보를 입력 받을 때 역방향 간선을 따로 입력 받아 보자

 

역방향으로 입력을 받으면 각 정점들(A)에서 X로 가는 최단거리를 X->A 최단거리로 바꿀 수 있다!

다익스트라 한 번이면 각 정점들에서 X로 가는 최단거리배열을 구할 수 있다는 것이다.

 

 

시간차이가 어마어마하게 많이 나는걸 볼 수 있다

---

2. 코드 - 최적화 X

#include <iostream>
#include <vector>
#include <queue>
 
#define pii pair<int, int>
 
using namespace std;
 
 
int N, M, X;
const int INF = 1e9+7;
vector<pii > graph[1001]; 
vector<int> dist;
int resdist[1001];
 
void input(){
    int u, v, t;
    cin >> N >> M >> X;
    for(int i = 0; i < M; i++){
        cin >> u >> v >> t;
        graph[u].push_back(make_pair(t, v));
    }
}
 
void Dijstra(int S){
    dist.clear();
    dist.resize(N+1, INF);
    
    dist[S] = 0;
    
    priority_queue<pii, vector<pii >, greater<pii > > que;
    que.push({0, S});
    
    while(!que.empty()){
        int min_cost = que.top().first;
        int now = que.top().second;
        que.pop();
        
        if(min_cost > dist[now]) continue;
        
        for(int i = 0; i < graph[now].size(); i++){
            int next = graph[now][i].second;
            int next_cost = min_cost + graph[now][i].first;
            
            if(next_cost < dist[next]){
                dist[next] = next_cost;
                que.push({next_cost, next});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    for(int i = 1; i <= N; i++){
        Dijstra(i);
        // i가 X로 가는 최단거리 half
        resdist[i] = dist[X];
    }
    Dijstra(X);
    int res = 0;
    for(int i = 1; i <= N; i++){
        resdist[i] += dist[i];
        res = max(res, resdist[i]);
    }
    
    cout << res;
    
    return 0;
}

 

---

2. 코드 - 최적화 O

#include <iostream>
#include <vector>
#include <queue>
 
#define pii pair<int, int>
 
using namespace std;
 
 
int N, M, X;
const int INF = 1e9+7;
vector<pii > graph[2][1001]; 
vector<int> dist[2];
int resdist[1001];
 
void input(){
    int u, v, t;
    cin >> N >> M >> X;
    for(int i = 0; i < M; i++){
        cin >> u >> v >> t;
        graph[0][u].push_back(make_pair(t, v));
        graph[1][v].push_back(make_pair(t, u));
    }
    dist[0].resize(N+1, INF);
    dist[1].resize(N+1, INF);
}
 
void Dijstra(int k){
    dist[k][X] = 0;
    
    priority_queue<pii, vector<pii >, greater<pii > > que;
    que.push({0, X});
    
    while(!que.empty()){
        int min_cost = que.top().first;
        int now = que.top().second;
        que.pop();
        
        if(min_cost > dist[k][now]) continue;
        
        for(int i = 0; i < graph[k][now].size(); i++){
            int next = graph[k][now][i].second;
            int next_cost = min_cost + graph[k][now][i].first;
            
            if(next_cost < dist[k][next]){
                dist[k][next] = next_cost;
                que.push({next_cost, next});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    
    // 정점들에서 X로 가는 최단거리
    Dijstra(1);
    
    // X에서 정점들로 가는 최단거리
    Dijstra(0);
    
    int res = 0;
    for(int i = 1; i <= N; i++){
        res = max(res, dist[0][i] + dist[1][i]);
    }
    
    cout << res;
    
    return 0;
}