#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
using namespace std;
typedef long long ll;
#include "escape_route.h"
struct Edge {
int u, v, id; ll l, c;
};
const int Inf = 1e9;
const ll Linf = 1e18;
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) {
vector <vector <Edge>> g(n);
for (int i = 0; i < m; ++i) {
g[A[i]].push_back({A[i], B[i], i, L[i], C[i]});
g[B[i]].push_back({B[i], A[i], i, L[i], C[i]});
}
vector <vector <ll>> cd(n, vector <ll> (n, Linf));
for (int st = 0; st < n; ++st) {
auto &d = cd[st];
d[st] = 0;
set <pair <ll, int>> q;
q.insert({d[st], st});
while (!q.empty()) {
int u = q.begin()->second;
q.erase(q.begin());
ll tm = d[u] % s;
for (auto e : g[u]) {
ll dist = d[u];
if (tm > e.c - e.l) {
dist += s - tm;
}
dist += e.l;
if (dist < d[e.v]) {
q.erase({d[e.v], e.v});
d[e.v] = dist;
q.insert({d[e.v], e.v});
}
}
}
}
vector <vector <int>> qs(n);
for (int i = 0; i < q; ++i) {
qs[U[i]].push_back(i);
}
for (int i = 0; i < n; ++i) {
sort(qs[i].begin(), qs[i].end(), [&] (int f, int s) {
return T[f] < T[s];
});
}
vector <ll> ans(q, Linf);
for (int st = 0; st < n; ++st) {
set <pair <ll, int>> ev;
vector <int> kill(m);
vector <ll> d(n, Linf);
ll prev_t = -1;
auto recalc = [&] (ll t) {
prev_t = t;
d.assign(n, Linf);
d[st] = t;
vector <int> used(n);
for (int it = 0; it < n; ++it) {
int u = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) continue;
if (u == -1 || d[i] < d[u]) {
u = i;
}
}
if (u == -1) break;
used[u] = 1;
ll tm = d[u] % s;
for (auto e : g[u]) {
ll dist = d[u];
if (tm > e.c - e.l) {
continue;
}
dist += e.l;
d[e.v] = min(d[e.v], dist);
}
}
for (int u = 0; u < n; ++u) {
for (auto e : g[u]) {
if (kill[e.id]) continue;
// d[u] + delta + l > e.c
// delta > e.c - d[u] - l
ll delta = e.c - d[u] - e.l + 1;
if (delta > 0) ev.insert({t + delta, e.id});
}
}
};
int uk = 0;
ev.insert({0, -1});
while (!ev.empty()) {
auto p = *ev.begin();
ev.erase(ev.begin());
if (p.second != -1 && kill[p.second]) continue;
if (p.second != -1) kill[p.second] = 1;
ll t = p.first;
while (uk < qs[st].size() && T[qs[st][uk]] < t) {
int id = qs[st][uk];
ans[id] = min(ans[id], d[V[id]] - prev_t);
for (int u = 0; u < n; ++u) {
ans[id] = min(ans[id], d[u] - prev_t + (s - (d[u] - prev_t + T[id]) % s) % s + cd[u][V[id]]);
}
++uk;
}
if (uk == (int)qs[st].size()) break;
recalc(t);
}
}
for (int i = 0; i < q; ++i) {
ans[i] = min(ans[i], cd[U[i]][V[i]] + (s - (T[i] % s)) % s);
}
return ans;
}
#ifdef LOCAL
#include <unistd.h>
#include <cassert>
#include <cstring>
namespace {
const int N_MAX = 90;
const int M_MAX = N_MAX * (N_MAX - 1) / 2;
const long long S_MAX = 1000000000000000;
const int Q_MAX = 3000000;
int digits(long long x) {
if (x < 10) {
return 1;
}
return digits(x / 10) + 1;
}
const int N_digits = digits(N_MAX);
const int M_digits = digits(M_MAX);
const int S_digits = digits(S_MAX);
const int Q_digits = digits(Q_MAX);
const int ABUV_digits = digits(N_MAX - 1);
const int LCT_digits = digits(S_MAX - 1);
const int answer_digits = 19;
int N, M, Q;
long long S;
std::vector<int> A, B, U, V;
std::vector<long long> L, C, T;
class Input {
private:
std::vector<char> buffer;
int pos;
int read_NABUV() {
if (buffer[pos + 1] == ' ') {
int x = buffer[pos] - '0';
pos += 2;
return x;
} else {
int x = (buffer[pos] - '0') * 10 + (buffer[pos + 1] - '0');
pos += 3;
return x;
}
}
long long read_number(char sep) {
long long x = 0;
while (true) {
if (buffer[pos] == sep) {
pos++;
break;
} else if (buffer[pos + 1] == sep) {
x = x * 10 + (long long)(buffer[pos] - '0');
pos += 2;
break;
} else {
x = x * 100 +
(long long)((buffer[pos] - '0') * 10 + (buffer[pos + 1] - '0'));
pos += 2;
}
}
return x;
}
public:
void read_all() {
int l1 = N_digits + 1 + M_digits + 1 + S_digits + 1 + Q_digits + 1;
int l2 =
(ABUV_digits + 1 + ABUV_digits + 1 + LCT_digits + 1 + LCT_digits + 1) *
M_MAX;
int l3 = (ABUV_digits + 1 + ABUV_digits + 1 + LCT_digits + 1) * Q_MAX;
int total_length = l1 + l2 + l3;
buffer.resize(total_length + 1);
size_t read_result =
read(0, buffer.data(), sizeof(char) * (total_length + 1));
assert(read_result <= sizeof(char) * (total_length + 1));
pos = 0;
N = read_NABUV();
M = read_number(' ');
S = read_number(' ');
Q = read_number('\n');
A.resize(M);
B.resize(M);
L.resize(M);
C.resize(M);
for (int i = 0; i < M; i++) {
A[i] = read_NABUV();
B[i] = read_NABUV();
L[i] = read_number(' ');
C[i] = read_number('\n');
}
U.resize(Q);
V.resize(Q);
T.resize(Q);
for (int j = 0; j < Q; j++) {
U[j] = read_NABUV();
V[j] = read_NABUV();
T[j] = read_number('\n');
}
}
};
void output(std::vector<long long>& answer) {
int total_length = (answer_digits + 1) * answer.size();
std::vector<char> buffer(total_length);
int pos = 0;
std::vector<char> tmp(answer_digits);
for (long long ans : answer) {
int p2 = answer_digits - 1;
while (true) {
if (ans < 10) {
tmp[p2] = char(ans) + '0';
break;
}
tmp[p2] = char(ans % 10) + '0';
ans /= 10;
p2--;
}
memcpy(buffer.data() + pos, tmp.data() + p2, answer_digits - p2);
pos += answer_digits - p2;
buffer[pos] = '\n';
pos++;
}
int write_result = write(1, buffer.data(), sizeof(char) * pos);
assert(write_result == pos);
}
} // namespace
int main() {
freopen("input.txt", "r", stdin);
Input().read_all();
std::vector<long long> answer = calculate_necessary_time(
N, M, S, Q, std::move(A), std::move(B), std::move(L), std::move(C),
std::move(U), std::move(V), std::move(T));
assert(answer.size() == (size_t)Q);
output(answer);
}
#endif
Compilation message
escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | while (uk < qs[st].size() && T[qs[st][uk]] < t) {
| ~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
65024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2816 ms |
111992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
65024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
65024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
65024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
