1753번: 최단경로

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


$O(v+e)$

그냥 다익스트라 알고리즘을 돌려도 되겠지만 이 풀이는 출제자의 의도가 아닐 것이다.
간선 가중치 길이의 최댓값이 작은 것을 주목하자.
길이가 x인 간선은 그 위에 인접한 가중치가 1인 x-1개의 노드를 생성시킬 수 있다.
모든 간선에 노드를 만들고 보면 전체 그래프는 간선 가중치가 단위 길이로 같게 되며
이러한 그래프에서는 BFS를 이용해 최단 거리를 구할 수 있다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int MXV = 2e4, MXE = 3e5;
int v, t, e, k, r[MXV + MXE * 9 + 1];
vector<int> adj[MXV + MXE * 9 + 1];
queue<int> q;
int main() {
    scanf("%d%d%d", &v, &e, &k);
    t = v;
    for (int i = 0, x, y, z; i<e; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (z<2) adj[x].push_back(y);
        else {
            adj[x].push_back(++t);
            for (; --z>1;) adj[t++].push_back(t + 1);
            adj[t].push_back(y);
        }
    }
    r[k] = 1;
    q.push(k);
    while (!q.empty()) {
        for (auto it : adj[q.front()]) if (!r[it]) r[it] = r[q.front()] + 1, q.push(it);
        q.pop();
    }
    for (int i = 1; i <= v; i++) r[i] ? printf("%d\n", r[i] - 1) : puts("INF");
    return 0;
}