mung3477   2년 전

안녕하세요.... 계속 틀려서 질문 드립니다.

s -> A -> B -> N

s -> B -> A -> N

두 경로의 최단 거리를 비교해서, 더 짧은 값을 출력했습니다.

각 구간의 최단 거리를 다익스트라 3번 돌려서 구했습니다.

경로가 없다  == dist가 업데이트 된 적이 없다 로 해서 INT_MAX와 비교했습니다.


반례 다 돌려 보고.. long long 틀린 것도 잡고.. 다 해봤는데도 안 되네요. 뭐가 틀린 걸까요?

mung3477   2년 전

visited를 쓰면 안됐네요..

최단거리를 구해야하니까, 같은 노드로 돌아오면 거리가 늘어나니 visited가 필요하다고 생각했는데, 실제로는 경로가 있지만 visited 때문에 정점으로 돌아오지 못해 경로가 없다고 생각하는 경우가 있었습니다.

momo6465   2년 전

visited 는 최단거리 갱신을 막는 요소라서 적절치 않지만 dist[cur.first] >= cur.second 인 경우에만 갱신하는 것으로 의도하신 최적화(?) 를 이룰 수 있을 것 같네요.

mung3477   2년 전

그런 방법도 있군요! 아이디어 감사드립니다.

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