5719번 - 거의 최단 경로
일단 최단 거리를 구하고, 그 경로 로 가는 길을 모두 Max값 500000 으로 해서 이용 안하게 하고, 최단 거리를 또 구하고 그게 처음 최단 거리와 같으면
또 그 졍로 Max 값 넣고 반복 하다가 만약 다른 최단 거리가 나오면 출력, 만약 가는 길이 없으면 -1 이 나오게 했는데, 문제를 풀고 시간 초과 나오길래...
다른 싸이트에 같은 문제가 있길래 그곳에서 제출 해보았는데 0.11 s 나왔는데 여기에서는 75% 에서 멈추더니 시간 초과 뜨더라구요 ㅜㅜ
이유를 모르겠어요 ㅜㅜ
시간 초과는 처음에 최단 거리를 찾지 못한 경우에 발생합니다.
첫 번째 다익스트라를 돌린 결과 d[end] = 500000 인 경우입니다.
그럼 처음 최단 거리가 없는 경우 에도 -1 를 출력 하는게 맞는건가요?
저도 똑같이 생각해서 풀었더니 틀렸어요 ㅠㅠ
어떤 경로를 공유하고 있는 최단경로가 여러 개 있을 때 그 경로를 모두 못지우는데 그거때문에 틀렸다고 뜨는거 같네여
홧팅
댓글을 작성하려면 로그인해야 합니다.
hj_d 8년 전
일단 최단 거리를 구하고, 그 경로 로 가는 길을 모두 Max값 500000 으로 해서 이용 안하게 하고, 최단 거리를 또 구하고 그게 처음 최단 거리와 같으면
또 그 졍로 Max 값 넣고 반복 하다가 만약 다른 최단 거리가 나오면 출력, 만약 가는 길이 없으면 -1 이 나오게 했는데, 문제를 풀고 시간 초과 나오길래...
다른 싸이트에 같은 문제가 있길래 그곳에서 제출 해보았는데 0.11 s 나왔는데 여기에서는 75% 에서 멈추더니 시간 초과 뜨더라구요 ㅜㅜ
이유를 모르겠어요 ㅜㅜ