백준 17835번 - 면접보는 승범이네 (C++)

https://www.acmicpc.net/problem/17835

17835번: 면접보는 승범이네

 

처음보는 유형의 다익스트라였다.

 

파티 문제처럼 역방향을 받아 다른 노드까지의 거리를 구하는 문제는 접한적이 있었기 때문에 핵심 아이디어는 캐치할 수 있었으나, 

 

K의 범위가 결국 N까지 올라올 수 있기 때문에 K번 다익스트라 처리를 하면 시간초과를 받을 수 밖에 없다.

 

여기서 처음 본 테크닉은 처음 다익스트라를 시작할 때 하나의 지점만 넣고 시작하는 것이 아니라 여러 지점을 넣고 한번에 다익스트라를 돌리는 것이다.

 

이렇게하면 하나의 지점이 아니라 집합에서 최소 거리를 구할 수 있다. 

 

그리고 지금 까지 난 다익스트라를 할 때 다음 노드를 보낼 때 

 

push({지금 코스트, 번호} 

 

를 푸쉬했는데 dist[now] + cost 식으로 쓰지 말고 cost를 계속 갱신해가며 가지고 다니면서 가지치기하는 것이 더 빠르다는 것을 알게되었다...

 

원래 내 방식대로 하니 시간초과가 발생했다. 그런데 의문은 이 문제는 1번의 다익스트라로 문제가 해결되는데 10만 N임에도 왜 시간초과가 발생한지 모르겠다.

 

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <queue>
#define ll long long
using namespace std;

vector<pair<ll, ll>> city[100001];

priority_queue<pair<ll, ll>> pq;

ll dist[100001];
ll N, M, K;

void dijk(){
    pair<ll, ll> result = {-1, -1}; // 번호, 거리 순
    
    while(!pq.empty()){
        ll nowPos = pq.top().second;
        ll nowCost = -pq.top().first;
        pq.pop();
        
        if(dist[nowPos] < nowCost) continue;
        
        for(ll i = 0; i < city[nowPos].size(); i++){
            ll next = city[nowPos][i].first;
            ll cost = city[nowPos][i].second + nowCost;
            
            if(dist[next] > cost){
                pq.push({-cost, next});
                dist[next] = cost;
            }
        }
    }
    
    for(ll i = 1; i <= N; i++){
        if(result.second < dist[i]){
            result = {i, dist[i]};
        }
    }
    
    cout << result.first << '\n' << result.second << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    for(ll i = 0; i <= N; i++) dist[i] = 1e18;

    for(ll i = 0; i < M; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        
        city[b].push_back({a, c});
    }
    
    for(ll i = 0; i < K; i++){
        ll s; cin >> s;
        pq.push({0, s});  
        dist[s] = 0;
    }
    
    dijk();
    
    return 0;
}