[platinum4] [해설,분류 미확인]22870 산책(Large)

아이디어는 어렵지 않은 다익스트람 문제다. 다만 나는 int로도 절대 오버플로우 나지 않을 거라 생각하고 맞왜틀 당하길래 한참 고민했는데... long 으로 변환하니 해결됬다.  500000 *  1000  * 2 에서 경로 하나만 더 추가하면 아슬아슬하게 넘어가나?

 

 

핵심은 사전순으로 최단거리를 구하는 것이다.

 

우선, i 부터 E까지의 거리를 구하기 위해 E부터 거꾸로 다익스트라를 구해야 한다.

그러면 , 모든 정점으로부터 E까지의 최단거리를 알 수 있다. 한 정점 (node) 에서 E까지의 최단거리를 fromE[ node] 라고 한다.

 

 

1번이 S(시작점)이라 하자. 1번에서 2번, 3번, 4번으로 갈 수 있다.

i번, j번 사이의 거리를 C[i][j]라 하자.

우선 C[1][2]  + fromE[2] ==   fromE[2] (E~1까지의 최단거리) 라면    1 -> 2번은 최단거리에 포함된 것이다. 

마찬가지로 3, 4번 노드에 대해서도   C[1][i] + fromE[i] == fromE[i]인지 확인한다. 

이 조건을 만족하는 노드 중 번호가 가장 작은 노드가 다음 방문 노드이다.

 

이제 2번노드에서, 다음 노드가 5,6,7번 노드라고 하면,

sum + C[2][i] + fromE[i] == fromE[i]  (i = 5,6,7 ,  sum =  2번노드로 올때까지의 거리의 합 )   의 조건을 만족하는 i중 최솟값을 다음 노드로 하면 된다.

 

여기서 의구심이 드는게,  다음노드~E까지의 최단경로 (fromE) 의 간선은 지금까지 거쳐온 노드를 방문 할 수도 있지 않을 까 라는 것이다.

 

즉 위의 경우,  fromE[2] 를 구성하는 경로들 중,   1,2번 노드를 방문하는 경우도 있지 않을까 라는 것이다. 

이를 테면 위와 같은 경우이다.  지금까지 1 -> 2번 경로를 지나왔고,  fromE[2] 가 만약 1번 경로를 지난다면 1 -> 2 -> 1-> ...   의 경로가 최단거리가 되는 셈이다. 그러나 간선이 모두 양수일 경우 최단거리에 사이클은 발생하지 않는다.  따라서 위의 경우 애초에 최단경로는 1->2->1->E 가 아닌 1->E 가 될 것이므로, fromE[1] = C[1][E]가 될 것이다.  따라서 C[1][2] + fromE[2] != fromE[1] 이 되므로 2번은 최단경로에 포함되지 않는다.

 

 

어쨌거나 저렇게 사전순 최소인 최단거리를 방문할 때마다 visit 배열에 저장하고,  

E부터 다시 다익스트라를 돌리며,  visit[node] == true인 곳은 방문하지 않으며 최단거리를 구하면 된다.

 

즉 

 E부터 S까지의 다익스트라  +   S부터 노드 순회하며 사전순 최단거리 구하기 + E부터 S까지 다익스트라(사전순 최단거리 피하며)

과정으로 구하면 된다.

 

 

아이디어는 어렵지 않았으나 long 형때매 또 한참 헤맨 문제였다. 자료형 때매 많이 호되게 당했으면서 또 당한게 매우 안타까웠다.

int로 해결될 줄 알았는데...