17396번 - 백도어
[43382506] https://www.acmicpc.net/source/43382506pq에서 (정점 번호, 거리) 순으로 비교하는 다익스트라?로, TLE가 나야 합니다.
아래 Python 코드로 만들어지는 데이터를 추가해 주세요.이 데이터는 '잘못 구현한 다익스트라'의 "이미 방문한 정점을 다시 방문"한 코드 저격 데이터를 약간 수정해서 만들었으며, ideone에서 테스트한 결과 TLE (5초 이상), 로컬에서 돌려본 결과 약 127초가 걸림을 확인하였습니다.
P.S. 잘못 구현한 다익스트라 글에 이 구현이 없는 건 의외네요.
(+ 실수로 질문 글에 올렸네요. 오타/오역/요청 으로 옮겼습니다.)
해당 글 작성자가 모자라서 강력한 케이스들을 첨부하지 못했습니다 죄송합니다 ㅠㅠ
아마 저 글을 쓸 당시에는 pair로 정점 정보를 구현하는 것 자체에 익숙하지 않아서 아예 그런 경우를 생각하지 못했던 것 같습니다. 지금 생각해 보면 그게 제일 많이 하는 실수인데...
아직도 추가할 데이터가 있군요 죄송합니다 ...
문제 조건을 지키지 않는 데이터입니다.
댓글을 작성하려면 로그인해야 합니다.
hibye1217 4년 전 9
[43382506] https://www.acmicpc.net/source/43382506
pq에서 (정점 번호, 거리) 순으로 비교하는 다익스트라?로, TLE가 나야 합니다.
아래 Python 코드로 만들어지는 데이터를 추가해 주세요.
이 데이터는 '잘못 구현한 다익스트라'의 "이미 방문한 정점을 다시 방문"한 코드 저격 데이터를 약간 수정해서 만들었으며, ideone에서 테스트한 결과 TLE (5초 이상), 로컬에서 돌려본 결과 약 127초가 걸림을 확인하였습니다.
P.S. 잘못 구현한 다익스트라 글에 이 구현이 없는 건 의외네요.
(+ 실수로 질문 글에 올렸네요. 오타/오역/요청 으로 옮겼습니다.)