| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125285 | Icelast | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct edge{
ll v, w, c;
};
vector<ll> dijkstra(int n, int s, ll T, ll S, vector<vector<edge>> &adj){
vector<ll> dist(n+1, INF);
dist[s] = T;
vector<bool> vis(n+1, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({T, s});
while(!pq.empty()){
ll d_u = pq.top().first;
int u = pq.top().second;
pq.pop();
if(vis[u]){
continue;
}
vis[u] = true;
for(auto it : adj[u]){
ll v = it.v, w = it.w, c = it.c;
if(vis[v]) continue;
ll cost;
if(d_u%S <= c-w){
cost = d_u+w;
}else{
cost = d_u+S-d_u%S+w;
}
if(dist[v] > cost){
dist[v] = cost;
pq.push({dist[v], v});
}
}
}
return dist;
}
void sub1(ll n, ll m, ll S, ll Q, vector<vector<edge>> adj){
for(int it = 1; it <= Q; it++){
ll u, v, t;
cin >> u >> v >> t;
u++; v++;
vector<ll> dist = dijkstra(n, u, t, S, adj);
cout << dist[v]-t << "\n";
}
}
void solve(){
ll n, m, S, Q;
cin >> n >> m >> S >> Q;
vector<vector<edge>> adj(n+1);
for(int i = 1; i <= m; i++){
ll u, v, w, c;
cin >> u >> v >> w >> c;
u++; v++;
adj[u].push_back({v, w, c});
adj[v].push_back({u, w, c});
}
if(Q <= 1000){
sub1(n, m, S, Q, adj);
return;
}
sub1(n, m, S, Q, adj);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("SYNDICATE.inp", "r", stdin);
//freopen("SYNDICATE.out", "w", stdout);
solve();
}