// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl
#else
#define bug(x)
#define cerr if (0) cerr
#endif
#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;
vector<i64> calculate_necessary_time(int N, int M, i64 S, int Q, vi A, vi B, vector<i64> L, vector<i64> C, vi U, vi V, vector<i64> T)
{
const int MAXN = 90, MAXM = MAXN*MAXN;
const i64 INF = 1e18;
static vi adj[MAXN];
for (int i = 0; i < M; i++) adj[A[i]].push_back(i), adj[B[i]].push_back(i);
static i64 dist[MAXN][MAXN], end[MAXN][MAXN];
for (int src = 0; src < N; src++) {
{
fill(dist[src], dist[src] + N, INF);
using X = pair<i64, int>;
priority_queue<X, vector<X>, greater<X>> pq;
auto ins = [&](int i, i64 d) {
if (dist[src][i] > d)
pq.push({dist[src][i] = d, i});
};
ins(src, 0);
while (sz(pq)) {
auto [d, i] = pq.top(); pq.pop();
if (dist[src][i] != d) continue;
for (int h : adj[i]) ins(i ^ A[h] ^ B[h], L[h] + (d % S <= C[h] - L[h] ? d : (d / S + 1) * S));
}
}
{
fill(end[src], end[src] + N, -1);
using X = pair<i64, int>;
priority_queue<X> pq;
auto ins = [&](int i, i64 d) {
if (end[src][i] < d)
pq.push({end[src][i] = d, i});
};
ins(src, S);
while (sz(pq)) {
auto [d, i] = pq.top(); pq.pop();
if (end[src][i] != d) continue;
for (int h : adj[i]) ins(i ^ A[h] ^ B[h], min(C[h], d) - L[h]);
}
}
}
vector<i64> ans(Q, INF);
for (int i = 0; i < Q; i++) for (int j = 0; j < N; j++) if (T[i] <= end[j][U[i]]) ans[i] = min(ans[i], S - T[i] + dist[j][V[i]]);
static i64 one[MAXM][MAXN], two[MAXM][MAXN], mid[MAXN]; int E = 0;
static bool vis[MAXN];
vector<tuple<i64, int, int>> upd;
for (int I = 0; I < N; I++) for (int H : adj[I]) {
int J = I^A[H]^B[H];
mid[E] = L[H];
{
fill(one[E], one[E]+N, INF);
fill(vis, vis+N, 0);
one[E][I] = 0;
for (int rep = 0; rep < N; rep++) {
int i = -1;
for (int j = 0; j < N; j++) if (one[E][j] < INF && (i == -1 || one[E][i] > one[E][j])) i = j;
if (i == -1) break;
vis[i] = 1;
for (int h : adj[i]) {
int j = i^A[h]^B[h];
i64 T = C[H]-L[H]-one[E][i];
if (T <= C[h]) one[E][j] = min(one[E][j], one[E][i]+L[h]);
}
}
}
{
fill(two[E], two[E]+N, INF);
fill(vis, vis+N, 0);
two[E][J] = 0;
for (int rep = 0; rep < N; rep++) {
int i = -1;
for (int j = 0; j < N; j++) if (two[E][j] < INF && (i == -1 || two[E][i] > two[E][j])) i = j;
if (i == -1) break;
vis[i] = 1;
for (int h : adj[i]) {
int j = i^A[h]^B[h];
i64 T = two[E][i]+C[H];
if (T <= C[h]-L[h]) two[E][j] = min(two[E][j], two[E][i]+L[h]);
}
}
}
for (int x = 0; x < N; x++) if (one[E][x] < INF) {
i64 T = C[H]-L[H]-one[E][x];
// assert(T >= 0);
upd.push_back({T, E, x});
}
E++;
}
vi perm(Q);
iota(all(perm), 0);
sort(all(perm), [&](int i, int j) {
return T[i]>T[j];
});
sort(all(upd), greater<>());
int p = 0;
static i64 other[MAXN][MAXN];
for (int i = 0; i < N; i++) fill(other[i], other[i]+N, INF);
for (int i : perm) {
while (p < sz(upd) && get<0>(upd[p]) >= T[i]) {
auto [T, E, x] = upd[p++];
for (int y = 0; y < N; y++) other[x][y] = min(other[x][y], one[E][x]+two[E][y]+mid[E]);
}
ans[i] = min(ans[i], other[U[i]][V[i]]);
}
return ans;
}
#ifdef LOCAL
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M, Q; i64 S; cin >> N >> M >> S >> Q;
vi A(M), B(M); vector<i64> L(M), C(M);
for (int i = 0; i < M; i++) cin >> A[i] >> B[i] >> L[i] >> C[i];
vi U(Q), V(Q); vector<i64> T(Q);
for (int i = 0; i < Q; i++) cin >> U[i] >> V[i] >> T[i];
auto ans = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
assert(sz(ans) == Q);
for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
65116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
858 ms |
155292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
65116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
65116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
65116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
