1504번 - 특정한 최단 경로
안녕하세요.... 계속 틀려서 질문 드립니다.
s -> A -> B -> N
s -> B -> A -> N
두 경로의 최단 거리를 비교해서, 더 짧은 값을 출력했습니다.
각 구간의 최단 거리를 다익스트라 3번 돌려서 구했습니다.
경로가 없다 == dist가 업데이트 된 적이 없다 로 해서 INT_MAX와 비교했습니다.
반례 다 돌려 보고.. long long 틀린 것도 잡고.. 다 해봤는데도 안 되네요. 뭐가 틀린 걸까요?
visited를 쓰면 안됐네요..
최단거리를 구해야하니까, 같은 노드로 돌아오면 거리가 늘어나니 visited가 필요하다고 생각했는데, 실제로는 경로가 있지만 visited 때문에 정점으로 돌아오지 못해 경로가 없다고 생각하는 경우가 있었습니다.
visited 는 최단거리 갱신을 막는 요소라서 적절치 않지만 dist[cur.first] >= cur.second 인 경우에만 갱신하는 것으로 의도하신 최적화(?) 를 이룰 수 있을 것 같네요.
그런 방법도 있군요! 아이디어 감사드립니다.
댓글을 작성하려면 로그인해야 합니다.
mung3477 2년 전
안녕하세요.... 계속 틀려서 질문 드립니다.
s -> A -> B -> N
s -> B -> A -> N
두 경로의 최단 거리를 비교해서, 더 짧은 값을 출력했습니다.
각 구간의 최단 거리를 다익스트라 3번 돌려서 구했습니다.
경로가 없다 == dist가 업데이트 된 적이 없다 로 해서 INT_MAX와 비교했습니다.
반례 다 돌려 보고.. long long 틀린 것도 잡고.. 다 해봤는데도 안 되네요. 뭐가 틀린 걸까요?