| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 393036 | 2021-04-22T15:17:05 Z | Mlxa | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
const int N = 92;
const int INF = 1e18;
struct edge {
int u;
int w;
int h;
edge(int x, int y, int z) : u(x), w(y), h(z) {}
operator int() {
return u;
}
};
int n, m, s, q;
vector<edge> g[N];
int dist[N];
bool used[N];
int near(int h) {
return (h + s - 1) / s * s;
}
int query(int v, int to, int t) {
fill_n(dist, N, INF);
fill_n(used, N, false);
dist[v] = t;
for (int it = 0; it < n; ++it) {
v = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) {
continue;
}
if (v == -1 || dist[v] > dist[i]) {
v = i;
}
}
used[v] = true;
for (edge u : g[v]) {
int can = dist[v] + u.w;
if (can % s > u.h || (can / s) > (dist[v] / s)) {
can = near(dist[v]) + u.w;
}
// cout << v << " " << u << " " << dist[v] << " " << can << endl;
if (dist[u] > can) {
dist[u] = can;
}
}
}
return dist[to] - t;
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> s >> q;
for (int a, b, l, c, i = 0; i < m; ++i) {
cin >> a >> b >> l >> c;
g[a].emplace_back(b, l, c);
g[b].emplace_back(a, l, c);
}
for (int v, u, t, i = 0; i < q; ++i) {
cin >> v >> u >> t;
cout << query(v, u, t) << "\n";
}
return 0;
}