# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1247541 | ASGA_RedSea | Train (APIO24_train) | C++17 | 0 ms | 0 KiB |
/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
ll solve(int n,int m,int w,vector <int> T,vector <int> x,vector <int> y,vector <int> A,vector <int> B,vector <int> C,vector <int> l,vector <int> r){
if(w == 0){
vector <vector <array <ll,4>>> a(n);
for(int i = 0;i < m;i++){
a[x[i]].push_back({y[i],A[i],B[i],C[i]});
}
vector <ll> d(n,inf);
vector <int> v(n,0);
priority_queue <array <ll,3>,vector <array <ll,3>>,greater <array <ll,3>>> q;
v[0] = 1;
d[0] = 0;
q.push({0,0,0});
while(!q.empty()){
ll i = q.top()[2];
ll t = q.top()[1];
q.pop();
for(auto& j : a[i]){
if(t <= j[1]){
d[j[0]] = min(d[j[0]],d[i] + j[3]);
if(v[j[0]] == 0){
v[j[0]] = 1;
q.push({d[j[0]],j[2],j[0]});
}
}
}
}
return (d[n-1] == inf ? -1 : d[n-1]);
}
return -1;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie();
int n,m,w;cin >> n >> m >> w;
vector <int> t(n),x(m),y(m),a(m),b(m),c(m),l(w),r(w);
for(auto& i : t)cin >> i;
for(auto& i : x)cin >> i;
for(auto& i : y)cin >> i;
for(auto& i : a)cin >> i;
for(auto& i : b)cin >> i;
for(auto& i : c)cin >> i;
for(auto& i : l)cin >> i;
for(auto& i : r)cin >> i;
cout << solve(n,m,w,t,x,y,a,b,c,l,r);
return 0;
}