| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 907440 | lighton | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct Edge{
int to;
ll t,c;
};
int N,M;
int S,Q;
vector<Edge> adj[101];
ll inf =1e18;
ll d[101];
ll dijk(int st ,int en , ll t){
forf(i,0,N) d[i] = inf;
d[st] = t;
priority_queue<pair<ll,int> > pq;
pq.push({-t,st});
while(pq.size()){
int now = pq.top().second;
ll nowt = -pq.top().first;
pq.pop();
if(d[now] < nowt) continue;
for(auto &edge : adj[now]){
ll newt;
if(nowt%S + edge.t <= edge.c) newt = nowt+edge.t;
else newt = S*((nowt/S)+1)+edge.t;
if(newt < d[edge.to]){
d[edge.to] = newt;
pq.push({-newt,edge.to});
}
}
}
return d[en]-t;
}
int main(){
scanf("%d %d %d %d" , &N,&M,&S,&Q);
forf(i,1,M){
int u,v; ll t,c;
scanf("%d %d %lld %lld" , &u,&v,&t,&c);
adj[u].push_back({v,t,c});
adj[v].push_back({u,t,c});
}
while(Q--){
int u,v; ll t;
scanf("%d %d %lld" , &u,&v,&t);
printf("%lld\n" , dijk(u,v,t));
}
}