[BOJ] K번째 최단경로 찾기

K번째 최단경로 찾기

TimeLimit	MemoryLimit	Condition	TAG
2s	256MB	(1 ≤ n ≤ 1000, 0 ≤ m ≤ 250000, 1 ≤ k ≤ 100, mk ≤ 3000000, 1 ≤ a,b,c ≤ n, 1 ≤ c ≤ 1000)	Dijkstra

다익스트라 응용 문제인데 굉장히 흔한 유형이여서 거의 20분 컷을 했는데.. 이런 유형이 딱 그런 느낌이에요 알면 바로 풀리고, 모르면 좀 걸리는?

또 이제 구현 한번 해보면 이런 문제들은 금방 접근도 되고, 거의 바로 풀리는거라서 그렇게 어렵진 않았습니다.

그래도 꽤 난이도가 높게 나오는 문제여서 조금 설명을 하고 마치겠습니다.

현재 노드에서 k번 초과로 방문할 필요가 없음! 왜냐하면 여기랑 이어져있는 노드들은 k번 방문할 수 있는 경우.. 이미 이 노드를 지나가거나 다른 경우임. 그래서 이걸로 최적화를 해주고요. 그리고 k번째 방문했다면! result 업데이트 해주고… 이런 순서는 priority_queue로 처리해서 간단히 다익스트라 돌리면 되구요.

마지막으로 중요한 것은 방문 안 하면 -1을 출력하는데 이때 예외 처리를 조금 조심해줘야 합니다. 왜냐하면 k=1이면, 1번 도시 즉 시작 도시는 0이 찍힙니다. 이때 그냥 print를 N_i = 0이면 -1을 출력하게 했다.. 그러면 이제 WA 뜨는겁니다. 뭐 이거는 문제를 읽고서 풀다보면 자연스럽게 해결할 수 있는 간단한 문제였구요.

재밌었습니다..

정답 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include<set>
#include <map>
using namespace std;
using ll = long long;

int inf = 1e9;

int n, m, k;
int graph[1001][1001];
int visited[1001];
ll result[1001];


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    
    for(int i = 0; i < m; i++){
        int a, b, c;
        
        cin >> a >> b >> c;
        
        graph[a][b] = c;
    }
    
    for(int i = 1; i <= n; i++) visited[i] = 0;
    
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    
    q.push({0, 1});
    
    while(!q.empty()){
        auto [cost, current] = q.top(); q.pop();
        
        if(visited[current] >= k) continue;
        visited[current]++;
        
        if(visited[current] >= k) result[current] = cost;
        
        for(int i = 1; i <= n; i++){
            if(graph[current][i] == 0 || visited[i] >= k) continue;
            
            q.push({graph[current][i] + cost, i});
        }
    }
    
    if(k == 1) cout << result[1];
    else {
        if(result[1] == 0) cout << -1;
        else cout << result[1];
    }
    cout << "\n";
    
    
    
    for(int i = 2; i <= n; i++){
        if(result[i] == 0) cout << -1;
        else cout << result[i];
        cout << "\n";
    }
    return 0;
}