Load to cocoa

$dist_+[i]:=$地点$1$から地点$i$へ移動する時の移動距離の総和の最小値
$dist_-[i]:=$地点$N$から地点$i$へ移動する時の移動距離の総和の最小値
とします．これらの配列の値はそれぞれ地点$1$,地点$N$を始点とするDijkstraのアルゴリズムによって高速に求めることができます．

よって題意である「地点$1$から地点$p_j$に移動し，地点$p_j$から地点$N$に移動し，地点$N$から地点$1$に移動する時の移動距離の総和の最小値」は 各$1 \leq j \leq K$に対して

• $\min (dist_+[p_j] + dist_-[p_j]) + dist_-[1]$

によって求めることができます．

問題全体としての時間計算量は$O( (N+M) \log N + K)$で，この問題の制約下では十分高速です．