elvpfhhrm   2년 전

10217번 문제를 11404 문제에서 학습했던 알고리즘으로 풀어보려고 시도하였으나 틀렸습니다 판정을 받았습니다.

아직 플로이드 와셜(?) 알고리즘에 대한 이해가 부족해 이전에 친 코드를 조금 수정해본 정도 이긴 합니다.

고수님들께 이 코드의 잘못된 점과 개선방법에 대한 조언을 부탁드리고 십습니다.

slah007   2년 전

모든 i->j 쌍에 대해 Cost 합이 M 이하일 때까지 무조건 Dist를 갱신하게 되는데, 이렇게 하면 더 Dist가 긴 대신 Cost가 적어서 결과적으로 갈 수 있는 경로를 놓치게 됩니다. 예를 들어 N=4, M=10이고 티켓이 다음과 같이 주어질 수 있습니다.

1 2 10 1

1 3 3 5

3 2 3 8

2 4 3 2

따라서 Dist가 최소인 것 중에서 Cost가 최소인 것이 아니라 모든 가능한 Cost에 대해 최소 거리를 봐야 합니다.

이때 Floyd-Warshall은 모든 정점 쌍 간의 거리를 구하는 알고리즘이기 때문에 이와 같이 A->B 경로 한 쌍에 대한 문제를 풀기에 부적합하며(그냥 100^3은 통과되지만 모든 Cost의 경우를 저장해 둔 * 10000이 붙으면 시간 초과입니다) Dijkstra 알고리즘을 사용하는 것이 좋습니다.


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