地点 \(1\) から地点 \(K\) への最短所要時間と、地点 \(K\) から地点 \(N\) への最短所要時間をそれぞれ独立に求め、その和が答えとなります。

よって地点 \(1,K\) をそれぞれ始点としたダイクストラ法を \(2\) 回行うことで答えを求めることができます。

また、与えられるグラフは無向グラフであることから、「地点 \(1\) から地点 \(K\) への最短所要時間」は「地点 \(K\) から地点 \(1\) への最短所要時間」と等しくなります。よって地点 \(K\) を始点としたダイクストラ法 \(1\) 回で答えを求めることもできます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  k--;
  vector<vector<pair<int, int>>>G(n);
  for(int i=0; i<m; i++){
    int u, v, c;
    cin >> u >> v >> c;
    u--;
    v--;
    G[u].push_back({v, c});
    G[v].push_back({u, c});
  }

  priority_queue<pair<long long, int>>q;
  vector<long long>dist(n, INF);
  dist[k] = 0;
  q.push({0, k});
  while(q.size() > 0){
    auto[d, v] = q.top(); q.pop();
    d = -d;
    if(dist[v] != d){
      continue;
    }
    for(auto[vv, c]: G[v]){
      if(dist[vv] > dist[v] + c){
        dist[vv] = dist[v] + c;
        q.push({-dist[vv], vv});
      }
    }
  }
  long long ans = dist[0] + dist[n-1];
  if(ans >= INF){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}

実装例 (Python)

import heapq

INF = 10**18
N, M, K = map(int, input().split())
K -= 1
G = [[] for _ in range(N)]
for _ in range(M):
  U, V, C = map(int, input().split())
  U -= 1
  V -= 1
  G[U].append((V, C))
  G[V].append((U, C))

q = [(0,K)]
dist = [INF]*N
dist[K] = 0
while len(q) > 0:
  d, v = heapq.heappop(q)
  if dist[v] != d:
    continue
  for vv, c in G[v]:
    if dist[vv] > dist[v] + c:
      dist[vv] = dist[v] + c
      heapq.heappush(q, (dist[vv], vv))

ans = dist[0] + dist[N-1]
if ans >= INF:
  print(-1)
else:
  print(ans)