1219번 - 오민식의 고민
만식이의 고민 41퍼센트에서 틀리는데 한번만 봐주세요 ㅠ
로직은
1. 두 도시 교통비용과 도시 방문시 얻는 비용을 간선에 통합
2. 플로이드 알고리즘으로 시작점에서 목적디 도착 가능 여부 확인
-> 불가능하면 gg출력
3. SFPA 알고리즘을 통해 최단거리 구하기(-하면 최대값)
-> 그 중에서 큐가 n번돌때 업데이트 되는 정점들 bfsQ에 저장
4. bfsQ 정점들을 bfs 해서 사이클들 모두 visited 체크
5. 사이클이고, 사이클에 dest가 있으면 ->Gee 출력
6. 그렇지 않으면 -간선의 최소값 + 시작점 도시에서 얻는 비용
왜 41퍼에서 틀릴까요?ㅠㅠ
저도 계속 41% 에서 틀렸었는데 저 같은 경우 반례는
5 0 0 0
1 2 3 4 5
ans : 1 이였습니다.
댓글을 작성하려면 로그인해야 합니다.
his130 6년 전
만식이의 고민 41퍼센트에서 틀리는데 한번만 봐주세요 ㅠ
로직은
1. 두 도시 교통비용과 도시 방문시 얻는 비용을 간선에 통합
2. 플로이드 알고리즘으로 시작점에서 목적디 도착 가능 여부 확인
-> 불가능하면 gg출력
3. SFPA 알고리즘을 통해 최단거리 구하기(-하면 최대값)
-> 그 중에서 큐가 n번돌때 업데이트 되는 정점들 bfsQ에 저장
4. bfsQ 정점들을 bfs 해서 사이클들 모두 visited 체크
5. 사이클이고, 사이클에 dest가 있으면 ->Gee 출력
6. 그렇지 않으면 -간선의 최소값 + 시작점 도시에서 얻는 비용
왜 41퍼에서 틀릴까요?ㅠㅠ