公式

D - 届け物 / Delivery 解説 by kyopro_friends 印刷ページ


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

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

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

実装例 (C++)

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

int main(){
  int n, m, s, g, t;
  cin >> n >> m >> s >> g >> t;
  s--, g--, t--;
  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[g] = 0;
  q.push({0, g});
  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[s] + dist[t];
  if(ans >= INF){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}

実装例 (Python)

import heapq

INF = 10**18
N, M, S, g, T = map(int, input().split())
S -= 1
g -= 1
T -= 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, g)]
dist = [INF]*N
dist[g] = 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[S] + dist[T]
if ans >= INF:
  print(-1)
else:
  print(ans)

投稿日時:
最終更新: