#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <chrono>
#include <bit>
#include <climits>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
signed main() {
int k, n, m, o;
cin >> k >> n >> m >> o;
int l = n / k + 1;
const int P = 16;
vector<vector<vvi>> dp(l, vector<vvi>(P, vvi(k, vi(k, LLONG_MAX / 2))));
loop(i, m) {
int a, b, t;
cin >> a >> b >> t;
dp[a / k][0][a % k][b % k] = t;
}
for (int p = 1; p < P; p++) {
for (int layer = 0; layer < l; layer++) {
if (layer + (1 << p) >= l)
continue;
const vvi& connector1 = dp[layer][p - 1];
const vvi& connector2 = dp[min(l, layer + (1 << (p - 1)))][p - 1];
vvi& connector = dp[layer][p];
for (int i1 = 0; i1 < k; i1++) {
for (int i2 = 0; i2 < k; i2++) {
for (int i3 = 0; i3 < k; i3++) {
connector[i1][i3] = min(connector[i1][i3], connector1[i1][i2] + connector2[i2][i3]);
}
}
}
}
}
loop(order, o) {
int a, b;
cin >> a >> b;
int l1 = a / k;
int l2 = b / k;
if (l1 == l2) {
cout << 0 << endl;
continue;
}
else if (l1 >= l2) {
cout << -1 << endl;
continue;
}
vi cost(k, LLONG_MAX / 2);
cost[a % k] = 0;
for (int p = P - 1; p >= 0; p--) {
int diff = l2 - l1;
if ((diff & (1 << p)) == 0)
continue;
const vvi& connector = dp[l1][p];
vi newCost(k, LLONG_MAX / 2);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
newCost[j] = min(newCost[j], cost[i] + connector[i][j]);
}
}
swap(cost, newCost);
l1 += (1 << p);
}
int ans = cost[b % k];
if (ans == LLONG_MAX / 2)
cout << -1 << endl;
else
cout << ans << endl;
}
}
# | 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... |