31913번 - 돈 복사
모든 간선을 n회씩 탐색. 탐색하며 갱신되는 지점은 route 리스트에 경로 전체를 저장, 갱신될 때마다 해당 경로를 지나갈 때 소지금의 최솟값을 route_min에 저장
새로운 갱신점이 route 내에 이미 존재하다면, cycle이 존재하므로 cycles set에 저장.
cycles에 저장된 각 cycle에 대해,
cycle의 모든 포지션의 route_min을 비교해 최솟값을 찾고,
다른 cycle들과 이를 비교해 ans를 계산
위 과정으로 풀었는데, 3%에서 계속 틀렸습니다가 나오네요 ㅜㅜ
대체 어디가 문제인 걸까요
0, 1, 3으로 가는 경로와 0, 2, 3으로 가는 경로가 존재하고, 3에서 사이클이 시작되는 상황에서0, 1, 3은 소지금이 0, -5, 5로 바뀌고, 0, 2, 3은 소지금이 0, -1000, 1000으로 바뀐다면visited[3]에 1000, routes[3]에 [0, 2, 3]이 저장돼서 안전도가 5가 아닌 1000으로 구해지는 문제가 있네요.
댓글을 작성하려면 로그인해야 합니다.
shjh0815 1년 전
모든 간선을 n회씩 탐색. 탐색하며 갱신되는 지점은 route 리스트에 경로 전체를 저장, 갱신될 때마다 해당 경로를 지나갈 때 소지금의 최솟값을 route_min에 저장
새로운 갱신점이 route 내에 이미 존재하다면, cycle이 존재하므로 cycles set에 저장.
cycles에 저장된 각 cycle에 대해,
cycle의 모든 포지션의 route_min을 비교해 최솟값을 찾고,
다른 cycle들과 이를 비교해 ans를 계산
위 과정으로 풀었는데, 3%에서 계속 틀렸습니다가 나오네요 ㅜㅜ
대체 어디가 문제인 걸까요