his130   6년 전

만식이의 고민 41퍼센트에서 틀리는데 한번만 봐주세요 ㅠ

로직은

1. 두 도시 교통비용과 도시 방문시 얻는 비용을 간선에 통합

2. 플로이드 알고리즘으로 시작점에서 목적디 도착 가능 여부 확인

-> 불가능하면 gg출력

3. SFPA 알고리즘을 통해 최단거리 구하기(-하면 최대값)

-> 그 중에서 큐가 n번돌때 업데이트 되는 정점들 bfsQ에 저장

4. bfsQ 정점들을 bfs 해서 사이클들 모두 visited 체크

5. 사이클이고, 사이클에 dest가 있으면 ->Gee 출력

6. 그렇지 않으면 -간선의 최소값 + 시작점 도시에서 얻는 비용


왜 41퍼에서 틀릴까요?ㅠㅠ


comseung18   4년 전

저도 계속 41% 에서 틀렸었는데 저 같은 경우 반례는

5 0 0 0

1 2 3 4 5

ans : 1 이였습니다.

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