Official
D - 配達ルートの最適化 / Optimizing Delivery Routes Editorial
by
D - 配達ルートの最適化 / Optimizing Delivery Routes Editorial
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;
}
posted:
last update:
