| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209437 | emptypringlescan | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n,m,q;
long long mod;
vector<pair<int,pair<long long,long long> > > adj[95];
long long stz[95][95];
vector<pair<long long,long long> > tim[95][95],dir[95][95];
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> mod >> q;
for(int i=0; i<m; i++){
int a,b;
long long c,d;
cin >> a >> b >> c >> d;
adj[a].push_back({b,{c,d}});
adj[b].push_back({a,{c,d}});
}
priority_queue<pair<long long,pair<long long,int> >,vector<pair<long long,pair<long long,int> > >,greater<pair<long long,pair<long long,int> > > > pq;
for(int i=0; i<95; i++){
for(int j=0; j<95; j++) stz[i][j]=1e18;
}
for(int i=0; i<n; i++){
pq.push({0,{0,i}});
stz[i][i]=0;
while(!pq.empty()){
long long a=pq.top().first,b=pq.top().second.first;
int c=pq.top().second.second;
pq.pop();
if(a>stz[i][c]) continue;
for(auto j:adj[c]){
long long nc=a+j.second.first;
if(nc%mod>j.second.second) nc=(a/mod+1)*mod+j.second.first;
if(stz[i][j.first]>nc){
pq.push({nc,{nc,j.first}});
stz[i][j.first]=nc;
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++) pq.push({stz[j][i],{mod,j}});
while(!pq.empty()){
long long a=pq.top().first,b=pq.top().second.first;
int c=pq.top().second.second;
pq.pop();
if(!tim[c][i].empty()&&tim[c][i].back().first>=b) continue;
tim[c][i].push_back({b,a});
for(auto j:adj[c]){
long long nt=min(b,j.second.second)-j.second.first;
if(nt<0) continue;
if(!tim[j.first][i].empty()&&tim[j.first][i].back().first>=nt) continue;
pq.push({a,{nt,j.first}});
}
}
}
for(int i=0; i<n; i++){
pq.push({0,{mod,i}});
while(!pq.empty()){
long long a=pq.top().first,b=pq.top().second.first;
int c=pq.top().second.second;
pq.pop();
if(!dir[c][i].empty()&&dir[c][i].back().first>=b) continue;
dir[c][i].push_back({b,a});
for(auto j:adj[c]){
long long nc=a+j.second.first;
long long nt=min(b,j.second.second)-j.second.first;
if(nt<0) continue;
if(!dir[j.first][i].empty()&&dir[j.first][i].back().first>=nt) continue;
pq.push({nc,{nt,j.first}});
}
}
}/*
for(int i=0; i<n; i++){
for(int o=0; o<n; o++){
cout << i << " to " << o << '\n';
for(auto j:tim[i][o]) cout << j.first << ' ' << j.second << " ";
cout << '\n';
}
cout << '\n';
}*/
while(q--){
int a,b;
long long c;
cin >> a >> b >> c;
pair<long long,long long> wt=*lower_bound(tim[a][b].begin(),tim[a][b].end(),make_pair(c,-1ll));
long long c1=wt.second+mod-c;
int p2=lower_bound(dir[a][b].begin(),dir[a][b].end(),make_pair(c,-1ll))-dir[a][b].begin();
long long c2=1e18;
if(p2<(int)dir[a][b].size()) c2=dir[a][b][p2].second;
cout << min(c1,c2) << '\n';
}
}