[백준 1854] K번째 최단경로 찾기 (C++)

1854번: K번째 최단경로 찾기

 

다익스트라 알고리즘을 큰 변형없이 그냥 사용하면 되는 문제이다.

 

  다익스트라 알고리즘에서는 현재까지 구한 시간보다 다음 정점까지 가는데 걸리는 시간이 더 긴 경우에만 다음 정점을 탐색하고, 걸리는 시간을 갱신한다. 따라서 이 조건을 빼는 경우에는 N 정점에 도달하는 경우는 무수히 많아지게 될 것이다. 다익스트라에서는 다음 정점으로 가는 시간이 가장 적은 간선부터 탐색하기 때문에 이를 응용하면, 특정 정점에 도달할 때마다 도달하는데 걸리는 시간을 다 모아본다면 시간이 순차적으로 늘어나있음을 알 수 있다.

 

따라서 특정 정점(dist[i])에 도달하는 경우를 최대 K번까지만 반복한다면 K번째 최단경로를 구할 수 있다.

 

i라는 정점의 K번째 최단경로를 구하기 위해서 다른 정점의 K + a 번째 최단경로가 필요한 경우가 있지 않을까 하는 의문을 가지고 제출을 했었다. 그런데 그냥 맞았다고 뜨길래 반례 몇 개를 그려보고, K번째 최단 경로를 찾기 위해서 다른 정점의 K+a 번째의 최단경로가 당연히 필요없다고 이해했다. K번째를 찾는데 뭐하러 K+a번째를 찾아야하나 라는 의문이 왜 들었는지 모르겠다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 2e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, K;
vector<pii > adj[1001];
vector<int> dist[1001];
 
void input(){
    cin >> N >> M >> K;
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
    }
}
 
struct cmp{
    bool operator()(pii &a, pii &b){
        return a.first > b.first;
    }
};
 
void dijkstra(){
    priority_queue<pii, vector<pii >, cmp> pq; 
    pq.push({0, 1});
    
    while(!pq.empty()){
        int now = pq.top().second;
        int now_time = pq.top().first;
        pq.pop();
        
        dist[now].push_back(now_time);
        if(dist[now].size() > K) continue;
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].second;
            int next_time = now_time + adj[now][i].first;
            
            pq.push({next_time, next});
        }
    }
}
 
void solve(){
    dijkstra();
    for(int i = 1; i <= N; i++){
        if(dist[i].size() < K) cout << -1 << "\n";
        else cout << dist[i][K-1] << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}