Official

E - 鉄道旅行 / Railway Trip Editorial by physics0523 Editorial for printing


\(2\) 人で \(K\) 円以内で到達するということは、 \(1\) 人で \(K/2\) 円(小数点以下切り捨て)以内で到達するということに言い換えられます。

ここで、本問題は以下の頂点からなる最短経路問題であるとみなすことができます。

  • 頂点 \((v,w)\) … 都市 \(v\) に消費金額 \(w\) で到達した状態。

上記の情報をひとつの頂点であるとみなして ダイクストラ法 を行うことで、時間計算量 \(O( (N+M)K\log(NK))\) でこの問題に正解することができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using a3=array<ll,3>;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  K/=2;
  vector<vector<a3>> g(N);
  for(ll i=0;i<M;i++){
    ll U,V,A,B,S,T;
    cin >> U >> V >> A >> B >> S >> T;
    U--; V--;
    g[U].push_back(a3{V,A,S});
    g[V].push_back(a3{U,A,S});
    g[U].push_back(a3{V,B,T});
    g[V].push_back(a3{U,B,T});
  }

  vector<vector<ll>> d(N,vector<ll>(K+1,8e18));
  priority_queue<a3,vector<a3>,greater<a3>> pq;
  d[0][0]=0;
  pq.push(a3{0,0,0});
  while(!pq.empty()){
    auto od=pq.top(); pq.pop();
    if(od[1]==N-1){cout << od[0] << "\n"; return 0;}
    if(d[od[1]][od[2]]!=od[0]){continue;}
    for(auto &nx : g[od[1]]){
      ll v=nx[0];
      ll w=od[2]+nx[1];
      ll t=od[0]+nx[2];
      if(w>K){continue;}
      if(d[v][w]>t){
        d[v][w]=t;
        pq.push(a3{t,v,w});
      }
    }
  }
  cout << "-1\n";
  return 0;
}

posted:
last update: