백준 5214:환승

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

백준 5214번 문제 환승이예요. 지금까지 풀었던 다익스트라 문제와는 많이 다른문제입니다. 정점끼리도 이어져있고, 하이퍼튜브끼리도 이어져있습니다. 이번문제의 쉬운 풀이법은! 기존의 문제대로 정점끼리 계산을 하되 하이퍼튜브도 정점으로 생각해서 계산해 주는것. 정점 + 하이퍼튜브로 계산하면 기존 다익스트라 문제와 비슷하게 풀 수 있어요!

*참고한 블로그 http://degurii.tistory.com/19

이렇게 보시면 1 -> T1 -> 3 -> T3 -> 6 ->T5 -> 9 인 경우와 1 -> T2 -> 5 -> T4 -> 6 ->T5 -> 9 인 경우가 있어요!

물론 T1 = N, T2 = N+1 .. 로 매칭된 정점을 이용하겠죠? 튜브로의 이동은 0, 정점으로의 이동은 1로 계산하면 최단 경로가 나와요!

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
#define endl '\n'
#define INF (static_cast<int>(1e9))
typedef pair<int, int> PAIR;
int main(void) {
    ios::sync_with_stdio(false);
    int N, K, M; cin >> N >> K >> M;
 
    priority_queue<PAIR> pq;
    vector<vector<int>> graph(N + M);
    vector<bool> visited(N + M, false);
    vector<int> cost(N + M, INF);
    //정점의 갯수를 N + M으로 생각하고
    //N이상은 튜브의 정점이라고 생각해요
 
    for (int m = 0; m < M; m++) {//총 M개의 튜브
        for (int k = 0; k < K; k++) {//각 튜브의 k개의 역
            int n; cin >> n; n--;
            graph[n].push_back(N + m);//n역은 m번째 튜브와 연결
            graph[N + m].push_back(n);//m번째 튜브는 n역과 연결
        }
    }
    
    pq.push(PAIR(-0, 0));
    cost[0] = 0;//시작점!
 
    while (!pq.empty()) {//다익스트라 알고리즘
        int cur;
        do {
            cur = pq.top().second; pq.pop();
        } while (pq.empty() && visited[cur]);
        if (visited[cur]) break;
        visited[cur] = true;
 
        for (auto& next : graph[cur]) {
            //N이상(튜브내 이동)은 이동거리 0, 역끼리는 이동거리 1
            int distance = next >= N ? 0 : 1;
            if (cost[next] > cost[cur] + distance) {
                cost[next] = cost[cur] + distance;
                pq.push(PAIR(-cost[next], next));
            }
        }
    }
 
    if (cost[N - 1] != INF) cout << cost[N - 1] + 1 << endl;
    else cout << -1 << endl;
    return 0;
}