filot   1년 전

PQ를 이용해서 최단경로를 구하고

2번째를 계속 갱신하도록 했는데

예제는 맞는데..

올리기만 하면 4%에서 틀렸습니다라고 하네요..

몇개 예제로 그려봐도 잘 나온느데.. 어떤 케이스에서 자꾸 문제가 되는건지... 

혹시 제가 고려하지 못한게 있는지 조언을 부탁드리겠습니다.

jjwdi0   1년 전

http://contest.usaco.org/TESTDATA/NOV06_6.htm

이곳에 채점데이터가 있습니다.

filot   1년 전

감사합니다.

그런데 테스트케이스를 보니 더 답답하네요.

Test 2의 경우 3 4 2046과 4 3 1395가 있네요.

이 문제 양방향으로 알고 있는데 왜 케이스가 저런게 주어지는지..ㅠㅠ

다른 분들 통과한거 보면 신기하네요.

jjwdi0   1년 전

쉽게 말해서, A에서 B로 가는 길이 두 갈래인 겁니다.

만약, 다음과 같은 입력이 있다고 생각합시다.


2 2

1 2 5

2 1 4


여기서 1에서 2로 가는 두 번째 최단경로는 5입니다. (첫 번째는 4겠죠.)

만약, 1에서 2로 가는 간선의 가중치가 15라면, '2 1 4'의 간선을 통해 1 -> 2-> 1 -> 2 의 경로가 두 번째 최단경로겠죠.

감이 잡히시나요? 제가 설명을 잘 못해서..ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.