#include "escape_route.h"
#include <algorithm>
#include <cassert>
#include <limits>
static const long long INF = 1e18;
static const int MAX_N = 61;
static const int MAX_M = 1771;
std::vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T) {
std::vector<long long> answer(Q, INF);
std::vector<std::vector<long long>> dists0(N);
for (int start = 0; start < N; ++start) {
std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1));
std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1));
for (int i = 0; i < M; ++i) {
l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
}
std::vector<long long> dist(N, INF);
std::vector<bool> used(N, false);
dist[start] = 0;
for (int it = 0; it < N; ++it) {
int u = -1;
for (int v = 0; v < N; ++v) {
if (!used[v] && (u == -1 || dist[v] < dist[u])) {
u = v;
}
}
assert(dist[u] != INF);
used[u] = true;
long long rem = dist[u] % S;
for (int v = 0; v < N; ++v) {
if (!used[v] && l[u][v] != -1) {
long long new_dist = dist[u] + l[u][v];
if (rem + l[u][v] > c[u][v]) {
new_dist = dist[u] + S - rem + l[u][v];
}
dist[v] = std::min(dist[v], new_dist);
}
}
}
dists0[start] = dist;
}
for (int start = 0; start < N; ++start) {
std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1));
std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1));
for (int i = 0; i < M; ++i) {
l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
}
std::vector<long long> stops = {0};
static long long dists[MAX_M][MAX_N];
while (true) {
static long long dist[MAX_N];
static bool used[MAX_N];
std::fill(dist, dist + N, INF);
std::fill(used, used + N, false);
dist[start] = 0;
for (int it = 0; it < N; ++it) {
int u = -1;
for (int v = 0; v < N; ++v) {
if (!used[v] && (u == -1 || dist[v] < dist[u])) {
u = v;
}
}
if (dist[u] == INF) break;
used[u] = true;
for (int v = 0; v < N; ++v) {
if (!used[v] && l[u][v] != -1) {
dist[v] = std::min(dist[v], dist[u] + l[u][v]);
}
}
}
long long stop = INF;
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
if (l[u][v] != -1) {
long long cur = c[u][v] - dist[u] - l[u][v] + 1;
if (cur <= stops.back()) {
l[u][v] = -1;
c[u][v] = -1;
} else {
stop = std::min(stop, cur);
}
}
}
}
std::copy(dist, dist + N, dists[(int) stops.size() - 1]);
stops.push_back(stop);
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
if (l[u][v] != -1 && c[u][v] - dist[u] - l[u][v] + 1 == stop) {
l[u][v] = -1;
c[u][v] = -1;
}
}
}
if (stop == INF) break;
}
for (int i = 0; i < Q; ++i) {
if (U[i] == start) {
int pos = std::upper_bound(begin(stops), end(stops), T[i]) - begin(stops);
answer[i] = std::min(answer[i], dists[pos - 1][V[i]]);
for (int W = 0; W < N; ++W) {
if (dists[pos - 1][W] != INF) {
answer[i] = std::min(answer[i], S - T[i] + dists0[W][V[i]]);
}
}
}
}
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1605 ms |
112028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
