2611번 - 자동차경주
알고리즘은 음수간선으로 만들고 벨만포드 n-1번 돌려서 최단거리 구하고,
이 과정에서 0으로 들어가는 간선은 종료간선이기 때문에 처리를 하지 않았습니다.
0으로 향하는 간선을 제외한 모든 간선이 완화되고,
각 정점에서 0으로 향할 수 있는 간선의 가중치를 자신의 거리에 대하여 가장 작은(음수로) 값을 찾구요
최종적으로 시작점과 연결을 해서 출력하는 형태인데
잘못된 부분이 어디있을까요?
확실하지는 않지만 0으로 들어오는 간선들 중에 중복간선이 있는 경우가 나오지 않을 것 같습니다.
41번째 줄에서 크기 비교를 하지 않고 넣기 때문에 큰 값이 무시될 수 있습니다.
감사합니다 해결됬습니다.
댓글을 작성하려면 로그인해야 합니다.
sksdong1 7년 전
알고리즘은 음수간선으로 만들고 벨만포드 n-1번 돌려서 최단거리 구하고,
이 과정에서 0으로 들어가는 간선은 종료간선이기 때문에 처리를 하지 않았습니다.
0으로 향하는 간선을 제외한 모든 간선이 완화되고,
각 정점에서 0으로 향할 수 있는 간선의 가중치를 자신의 거리에 대하여 가장 작은(음수로) 값을 찾구요
최종적으로 시작점과 연결을 해서 출력하는 형태인데
잘못된 부분이 어디있을까요?