| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1139198 | Math4Life2020 | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 90; const ll INF = 1e18;
pii adj[Nm][Nm]; //{travel time, latest leaving time}
vector<pii> dp[Nm][Nm]; //{latest leaving time, travel time}
ll dp3[Nm][Nm]; //time if leaving at start of day
ll rup(ll x, ll S) {
ll y = x/S;
if (x>(y*S)) {
return (y+1)*S;
} else {
return x;
}
}
vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A,
vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) {
for (ll i=0;i<Nm;i++) {
for (ll j=0;j<Nm;j++) {
adj[i][j]={INF,-INF};
}
}
for (ll m=0;m<M;m++) {
adj[A[m]][B[m]]={L[m],C[m]-L[m]};
adj[B[m]][A[m]]=adj[A[m]][B[m]];
}
for (ll x=0;x<N;x++) {
for (ll y=0;y<N;y++) {
if (x==y || adj[x][y].first==INF) {
continue;
}
vector<ll> dp2(N,INF);
vector<bool> pr2(N,false); //is processed
dp2[y]=adj[x][y].first+adj[x][y].second;
while (1) {
ll zc = -1; ll tc = INF;
for (ll z=0;z<N;z++) {
if (!pr2[z] && dp2[z]<tc) {
zc = z; tc = dp2[z];
}
}
if (zc == -1) {
break;
}
pr2[zc]=1;
for (ll z1=0;z1<N;z1++) {
if (tc<=adj[zc][z1].second) {
dp2[z1] = min(dp2[z1],tc+adj[zc][z1].first);
}
}
}
vector<ll> dp1(N,-INF);
vector<bool> pr1(N,false);
dp1[x]=adj[x][y].second;
while (1) {
ll zc = -1; ll tc = -INF;
for (ll z=0;z<N;z++) {
if (!pr1[z] && dp1[z]>tc) {
zc = z; tc = dp1[z];
}
}
if (zc==-1) {
break;
}
pr1[zc]=1;
for (ll z1=0;z1<N;z1++) {
if (tc<=(adj[z1][zc].first+adj[z1][zc].second) && (tc-adj[zc][z1].first)>=0LL) {
dp1[z1] = max(dp1[z1],tc-adj[zc][z1].first);
}
}
}
for (ll a=0;a<N;a++) {
for (ll b=0;b<N;b++) {
if (a!=b && dp1[a]!=-INF && dp2[b]!=INF) {
dp[a][b].push_back({dp1[a],dp2[b]-dp1[a]});
}
}
}
}
}
for (ll x=0;x<N;x++) {
for (ll y=0;y<N;y++) {
dp3[x][y]=INF;
if (x==y || dp[x][y].size()==0) {
continue;
}
//dp: {latest leaving time, travel time}
//dptw: {travel time, latest leaving time}
vector<pii> dptw;
for (pii p0: dp[x][y]) {
dptw.push_back({p0.second,p0.first});
}
sort(dptw.begin(),dptw.end());
dp[x][y].clear();
ll llt0 = -INF;
for (pii p0: dptw) {
if (p0.second>llt0) {
llt0 = p0.second;
dp[x][y].push_back({p0.second,p0.first});
}
}
dp3[x][y]=dptw[0].first;
}
}
for (ll k=0;k<N;k++) {
for (ll i=0;i<N;i++) {
for (ll j=0;j<N;j++) {
if (i==j) {
continue;
}
dp3[i][j]=min(dp3[i][j],rup(dp3[i][k],S)+dp3[k][j]);
}
}
}
vector<ll> ansv; //ans vector
for (ll q=0;q<Q;q++) {
ll ans = INF;
ll x = U[q]; ll y = V[q]; ll t0 = T[q];
auto A0 = lower_bound(dp[x][y].begin(),dp[x][y].end(),(pii){t0,-INF});
if (A0 != dp[x][y].end()) {
ans = (*A0).second;
}
for (ll z=0;z<N;z++) {
if (dp[x][z].size()>0 && dp[x][z].back().first>=t0) {
ans = min(ans,S-t0+dp3[z][y]);
}
}
ans = min(ans,S-t0+dp3[x][y]);
ansv.push_back(ans);
}
return ansv;
//exit(0);
}
int main() {
int N_,M_,S_,Q_; cin >> N_ >> M_ >> S_ >> Q_;
vector<int> A_,B_,U_,V_;
vector<ll> L_,C_,T_;
for (ll i=0;i<M_;i++) {
ll a0,b0,l0,c0; cin >> a0 >> b0 >> l0 >> c0;
A_.push_back(a0);
B_.push_back(b0);
L_.push_back(l0);
C_.push_back(c0);
}
for (ll i=0;i<Q_;i++) {
ll u0,v0,t0; cin >> u0 >> v0 >> t0;
U_.push_back(u0);
V_.push_back(v0);
T_.push_back(t0);
}
vector<ll> finans = calculate_necessary_time(N_,M_,S_,Q_,A_,B_,L_,C_,U_,V_,T_);
for (ll x: finans) {
cout << x << "\n";
}
}