tmd3283   2년 전

질문에 올라온 알고리즘 대로 구현했습니다.

가중치를 모두 2배하고 속도가 두배일 때는 가중치의 /2하고 속도가 느릴 때는 가중치의 *2로 해서 dijkstra로 구현했습니다.

이때 dist2의 배열을 이차원으로 해서 dist2[here][0]은 짝수번의 edge를 통해서 왔다는 것이고

dist2[here][1]은 홀수번의 edge를 통해서 왔다는 의미입니다.

ryute   2년 전

47번째 줄에서 두 정점의 거리를 모두 0으로 초기화하면 안 됩니다. 한 바퀴 돌아서 정점 1으로 이동 한 다음 길/짧으로 이동하는 것이 최적일 수도 있습니다.

tmd3283   2년 전

47번째 줄은 늑대의 다익스트라인데 정점을.모두 1씩 빼서 시작점 1이 0으로 했는데요

이 때 한바퀴를 돌아서 가는.것이 최적인 경우가 있나요??

tmd3283   2년 전

고민하다가 깨달았습니다.

만약 input이

5 5

1 2 1

1 4 5

1 5 3

4 5 4

2 3 400

으로 주어진다면 3까지의 최단거리를 dist2[start][1]=0으로 한다면 잘못 구하게 됩니다.

감사합니다.

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