公式

D - 配達ルートの最適化 / Optimizing Delivery Routes 解説 by physics0523


この問題の本質は標準的な最短経路問題です。
辺の情報を全て受け取って、速度規制のかかった辺の所要時間を \(2\) 倍してから最短経路問題を解けばよいです。

実装例ではダイクストラ法を用いています。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

const ll big=2e18;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> U(M),V(M),W(M);
  for(ll i=0;i<M;i++){
    cin >> U[i] >> V[i] >> W[i];
    U[i]--; V[i]--;
  }
  for(ll i=0;i<K;i++){
    ll C;
    cin >> C;
    C--;
    W[C]*=2ll;
  }
  vector<vector<pl>> g(N);
  for(ll i=0;i<M;i++){
    g[U[i]].push_back({V[i],W[i]});
    g[V[i]].push_back({U[i],W[i]});
  }

  vector<ll> d(N,big);
  priority_queue<pl,vector<pl>,greater<pl>> pq;
  d[0]=0;
  pq.push({0,0});
  while(!pq.empty()){
    auto od=pq.top(); pq.pop();
    if(d[od.second]!=od.first){continue;}
    for(auto &nx : g[od.second]){
      ll nd=d[od.second]+nx.second;
      if(d[nx.first]>nd){
        d[nx.first]=nd;
        pq.push({d[nx.first],nx.first});
      }
    }
  }

  if(d[N-1]==big){d[N-1]=-1;}
  cout << d[N-1] << "\n";
  return 0;
}

投稿日時:
最終更新: