채점번호 31760245: https://www.acmicpc.net/source...

https://www.acmicpc.net/board/...에도 제기되어있듯이, 본 문제에는 '중복된 간선은 주어지지 않는다'라는 조건이 없습니다. 만약 이 조건이 명시적으로 주어지지 않음에도 테스트케이스에서 중복된 간선을 주지 않는 경우(이는 https://www.acmicpc.net/board/...에서 증명된 사실입니다), 위에 첨부된 소스 코드와 같이 비효율적으로 구현된 다익스트라 코드가 본 문제를 정상적으로 통과할 수 있게 됩니다.

이에 따라, 아래의 <수정>대로 조건을 추가해주시거나, 또는 아래 소스 코드로 생성되는 테스트케이스를 추가해주세요. 채점환경에서도 시간이 많이 걸릴 지에 대해서 정확히 테스트하진 못했지만, 본 소스 코드가 아래의 테스트케이스에서 매우 많은 시간이 걸릴 것을 증명하였고, 로컬 환경에서 위 채점에 사용된 소스 코드에 대하여 매우 많은 시간이 걸리는 것을 확인하였습니다.

<수정 전>

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

<수정 후>

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000) 각 도시 사이에는 도로가 최대 1개 존재한다.

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작 도시이다.