[문제 요약] 사과 2 개를 그래프 상의 길을 따라 두 곳으로 배달하려고 한다. 가장 빠른 길을 찾는 것이 문제이다.
입력으로
9 7 5 1 4 // 9 개의 길 .7 개의 정점 . 5 번 정점에서 출발하여 두 정점 1 , 4 번 으로 배달(방문) 5 1 7 6 7 2 4 7 2 5 6 1 5 2 4 4 3 2 1 2 3 3 2 2 2 6 3모든 정점은 연결되어 있고 , 양 방향 길이고 길의 합은 2,000,000,000 을 넘지 않는다.
3 2 2 [1]-----[2]------[3]-----[4] \ / \ / 7\ /4 \3 /2 \ / \ / [5]-----[6]------[7] 1 25 번 정점에서 1 번 , 4 번 정점을 방문해야 한다면 아래의 길이 최적이고 비용의 합은 12
5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*
What is the minimum total distance Bessie must travel to deliver both apples by starting at pasture PB (1 <= PB <= P) and visiting pastures PA1 (1 <= PA1 <= P) and PA2 (1 <= PA2 <= P) in any order. All three of these pastures are distinct, of course.
Consider this map of bracketed pasture numbers and cowpaths with distances:
3 2 2 [1]-----[2]------[3]-----[4] \ / \ / 7\ /4 \3 /2 \ / \ / [5]-----[6]------[7] 1 2If Bessie starts at pasture [5] and delivers apples to pastures [1] and [4], her best path is:
5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*with a total distance of 12.
입력 9 7 5 1 4 5 1 7 6 7 2 4 7 2 5 6 1 5 2 4 4 3 2 1 2 3 3 2 2 2 6 3 출력 12
출처:usaco 2010 DEC silver