| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1316081 | vlomaczk | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include "escape_route.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
std::vector<long long> calculate_necessary_time(
ll N, ll M, long long S, ll Q, std::vector<ll> A, std::vector<ll> B,
std::vector<long long> L, std::vector<long long> C, std::vector<ll> U,
std::vector<ll> V, std::vector<long long> T) {
vector<ll> K(M);
for(ll i=0; i<M; ++i) K[i] = C[i] - L[i];
vector<ll> ans(Q);
vector<vector<ll>> queries(N);
for(ll i=0; i<Q; ++i) {
queries[U[i]].push_back(i);
}
vector<vector<pair<ll, ll>>> g(N);
for(ll i=0; i<M; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
ll inf = 1e18;
auto get_dists = [&](ll s) {
vector<ll> dist(N, inf), vis(N,0);
dist[s] = 0;
while(1) {
pair<ll, ll> best = {inf,0};
for(ll i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i});
if(best.first == inf) break;
auto[dv,v] = best;
vis[v] = 1;
for(auto[u,k] : g[v]) {
ll w = L[k];
ll t = dv%S;
if(t > K[k]) w += S-t;
if(dist[u] > dist[v] + w) {
dist[u] = dist[v] + w;
}
}
}
return dist;
};
vector<vector<ll>> dist(N);
for(ll i=0; i<N; ++i) dist[i] = get_dists(i);
for(ll i=0; i<N; ++i) sort(g[i].begin(), g[i].end(), [&](pair<ll, ll> x, pair<ll, ll> y){
return K[x.second] < K[y.second];
});
vector<vector<pair<ll, ll>>> oldg = g;
for(ll s=0; s<N; ++s) {
g = oldg;
sort(queries[s].begin(), queries[s].end(), [&](ll i, ll j) {
return T[i] > T[j];
});
vector<ll> best(M, S), parent(M,-1);
vector<ll> green;
vector<set<ll>> got(M);
auto zmien = [&](ll x, ll diff){
queue<ll> pq;
pq.push(x);
while(pq.size()) {
ll v = pq.front(); pq.pop();
best[v] -= diff;
for(auto u : got[v]) pq.push(u);
}
};
green.push_back(s);
best[s] = S;
for(auto idx : queries[s]) {
ll res = inf;
ll diff = best[s] - T[idx];
for(auto x : green) best[x] -= diff;
queue<ll> Q;
for(auto x : green) Q.push(x);
while(Q.size()) {
ll x = Q.front(); Q.pop();
while(g[x].size()) {
auto[u,i] = g[x].back();
if(best[x] <= K[i]) {
if(best[u]==S) {
green.push_back(u);
}
Q.push(u);
if(best[u] > best[x] + L[i]) {
ll DD = best[u] - (best[x] + L[i]);
zmien(u,DD);
if(parent[u]!=-1) got[parent[u]].erase(u);
got[x].insert(u);
parent[u] = x;
}
g[x].pop_back();
} else break;
}
}
// for(ll i=0; i<N; ++i) cout << best[i] << " "; cout << "\n";
for(auto x : green) {
if(x==V[idx]) {
res = min(res, best[x]);
}
res = min(res, (best[x]==0 ? 0 : S) + dist[x][V[idx]]);
}
ans[idx] = res - T[idx];
}
}
return ans;
}
int main() {
ll n,m,s,q;
cin >> n >> m >> s >> q;
vector<ll> A(m),B(m);
vector<ll> L(m),C(m);
for(ll i=0; i<m; ++i) cin >> A[i] >> B[i] >> L[i] >> C[i];
vector<ll> U(q), V(q);
vector<ll> T(q);
for(ll i=0; i<q; ++i) cin >> U[i] >> V[i] >> T[i];
for(auto x : calculate_necessary_time(n,m,s,q,A,B,L,C,U,V,T)) {
cout << x << "\n";
}
}