oVeron

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라를 통해 한 노드에서 다른 노드로 거리 완화를 시도하는 과정에서, 2가지 방법이 있음을 알 수 있다. 1. 포장을 하지 않는다. 2. 포장을 한다. 1번을 택할 경우 평범하게 다익스트라로 거리 완화를 하면 된다. 2번을 택할 경우, 포장을 한 번 했다는 사실을 저장한 후 거리 완화를 해야 한다. 이 포장을 한 번 했다는 사실을 저장하기 위해, 원래 1차..

알고리즘/baekjoon 2023. 1. 19. 19:44