// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int MAX_N = 5e4;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template <class X, class Y>
bool minimize(X &x, const Y &y) {
if (x <= y) return false;
x = y;
return true;
};
int n, q, m, k;
vector<ii> queries;
vector<ii> adj[MAX_N + 5];
namespace SUBTASK_1 {
const int N = MAX_N;
const int K = 1;
int numChains;
int lab[N + 5];
ll pref[N + 5];
void dfs(int u) {
lab[u] = numChains;
for (ii e : adj[u]) {
int v = e.first, w = e.second;
pref[v] = pref[u] + w;
dfs(v);
};
};
void Solve() {
for (int u = 0; u < n; u++) {
if (!lab[u]) {
++numChains;
dfs(u);
};
};
for (const ii &q : queries) {
int u = q.first, v = q.second;
if (lab[u] != lab[v]) {
cout << -1 << '\n';
} else {
cout << pref[v] - pref[u] << '\n';
};
};
};
}; // namespace SUBTASK_1
namespace SUBTASK_234 {
const int N = MAX_N;
int ans[N + 5], dist[N + 5];
bool inQueue[N + 5];
vector<ii> qu[N + 5];
bool checkSubtask() {
if (q <= 3000) return true;
for (const ii &query : queries)
if (query.first != 0) return false;
return true;
};
void spfa(int s) {
for (int u = 0; u < n; u++) dist[u] = INF;
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for (ii e : adj[u]) {
int v = e.first, w = e.second;
if (minimize(dist[v], dist[u] + w)) {
if (!inQueue[v]) {
inQueue[v] = true;
q.push(v);
};
};
};
};
};
void Solve() {
for (int i = 0; i < q; i++) {
int u = queries[i].first, v = queries[i].second;
qu[u].push_back(make_pair(v, i));
};
for (int u = 0; u < n; u++) {
if (qu[u].empty()) continue;
spfa(u);
for (const ii &q : qu[u]) {
int v = q.first, idx = q.second;
ans[idx] = (dist[v] == INF ? -1 : dist[v]);
};
};
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
};
}; // namespace SUBTASK_234
namespace SUBTASK_5 {
const int N = MAX_N;
struct Matrix {
int c[5][5];
Matrix() {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++) c[i][j] = INF;
};
Matrix operator*(const Matrix &other) const {
Matrix res;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
minimize(res.c[i][j], c[i][k] + other.c[k][j]);
};
};
};
return res;
};
void print() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << c[i][j] << ' ';
};
cout << endl;
};
};
} st[18][N + 5];
void Solve() {
for (int u = 0; u < n; u++) {
for (ii e : adj[u]) {
int v = e.first, w = e.second;
st[0][u / k].c[u % k][v % k] = w; // min dist (u, v) from layer (u/k) to (layer(v/k) = layer(u/k + 2^0))
};
};
int lim = (n + k - 1) / k;
for (int j = 0; (1 << j) <= lim; j++) {
for (int layer = 1; layer + (1 << j) - 1 <= lim; layer++) {
st[j][layer] = st[j - 1][layer] * st[j - 1][layer + (1 << (j - 1))];
};
};
for (const ii &q : queries) {
int u = q.first, v = q.second;
int layerU = u / k;
int layerV = v / k;
if (layerU >= layerV) {
cout << (u == v ? 0 : -1) << '\n';
continue;
};
int d = layerV - layerU;
Matrix ans;
for (int i = 0; i < 5; i++) ans.c[i][i] = 0;
int curLayer = layerU;
for (int j = 0; (1 << j) <= layerV; j++) {
if (d >> j & 1) {
ans = ans * st[j][curLayer];
curLayer += 1 << j;
};
};
int res = ans.c[u % k][v % k] == INF ? -1 : ans.c[u % k][v % k];
cout << res << '\n';
};
};
}; // namespace SUBTASK_5
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("MAIN.INP", "r")) {
freopen("MAIN.INP", "r", stdin);
freopen("MAIN.OUT", "w", stdout);
};
cin >> k >> n >> m >> q;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(ii(v, w));
};
queries.resize(q);
for (ii &query : queries) cin >> query.first >> query.second;
SUBTASK_5::Solve();
};
Compilation message (stderr)
toll.cpp: In function 'int main()':
toll.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
202 | freopen("MAIN.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | freopen("MAIN.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |