[일반] 형님들 백준 5719번 좀 도와주십쇼 저 잠못잡니다

[낄룩새(deliciousqoo)]

https://www.acmicpc.net/board/view/134755

Baekjoon Online Judge

웬만한 반례 다맞아서 방법은 맞는거같은데

시간초과 떠서 뭔가 최적화 하는방법 알고싶슴다

[익명(121.165)]

슥 보니까 다익스트라 조금 변형하면 될 거 같은데

[익명(124.5)]

dfs 로 간선 지워서 그런거 같은디... 만약 s->d 까지 가는 경로 중 하나만 "거의최단경로" 고 나머지가 싹 다 최단경로면 지우는데 M^2 걸림

[낄룩새(deliciousqoo)]

그 케이스가 확실히 문제가 되겠네요 경로저장이 dfs가 제일 적합할 줄 알았는데 다른 방법 생각해봐야할듯

[익명(182.226)]

dfs를 역방향으로 시행하면 바로 풀릴듯