公式
E - 鉄道旅行 / Railway Trip 解説
by
E - 鉄道旅行 / Railway Trip 解説
by
physics0523
印刷ページ
\(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;
}
投稿日時:
最終更新:
