4. 추가 테스트케이스

https://joey09.tistory.com/ent...

66% 에서 시간초과가 나는 경우

다익스트라 안에 이미 작은 값을 찾은 경우 continue를 넣어보세요. (전체코드 참조_

시간 초과가 나는 테케를 만들고 싶었지만 너무 큰 수라 렉걸리네요. ㅠㅠ

        <i># 다익스트라에서 시간초과 처리하는 방법.</i>
        <i># if dist[pos]<cost:</i>
        <i>#     continue</i>

6 6 2 8
1 2 7 11 5 1
1 1 9 
2 3 8 
5 1 7 
5 3 8 
4 5 8 
6 5 7

답 28

8 23 10 52
1 24 17 31 10 20 15 1
5 2 82 
3 6 58 
7 6 92 
7 4 72 
8 1 90 
2 3 80 
5 1 79 
5 3 81 
4 5 88 
6 5 72 
6 4 85 
3 5 58 
3 7 51 
3 8 65 
2 6 77 
1 2 96 
1 5 68 
7 2 74 
8 4 52 
2 7 75 
8 5 78 
1 4 90 
8 7 80

답; 192

8 14 2 6
1 2 7 11 5 9 15 1
4 7 9
2 1 5 
4 1 9 
6 8 8 
3 1 9 
1 6 6 
7 1 6 
6 7 5 
7 5 8 
6 1 5 
2 5 7 
8 2 5 
6 3 5
4 3 6

답 52

8 7 2 3
1 2 7 11 5 9 15 1
6 7 9 
7 5 8 
6 1 4 
2 5 1 
8 2 5 
6 3 5 
5 2 2

답 -9