가중치 최대값 / 가중치 최소값의 비율이 k라면 다익스트라가 O(V + kE)에 된대


방법은 최소 가중치가 a라고 하면 가중치 b인 간선 u -> v에 대해서


b / a = m이면


u -> u1 (가중치 a)

u1 -> u2 (가중치 a)

...

u_(m-1) -> u_m (가중치 a)

u_m -> v (가중치 b - m * a)


식으로 만든다음에 bfs 돌리는거임



이거 백준에 있나? 풀어보고 싶네