| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1128923 | pcheloveks | Toll (BOI17_toll) | C++17 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#include <iostream>
#include <vector>
#include <map>
#include <sstream>
#include <string>
#include <set>
#include <fstream>
#include <algorithm>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const LL DIM = 50007;
const LL INF = 999999999999;
LL n, k, o, m;
class edge {
public:
LL to, w;
};
vector < edge > v[DIM];
class tran {
public:
LL mat[5][5];
void init() {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
mat[i][j] = INF;
}
}
}
};
tran solve(LL L, LL R) {
tran ans;
ans.init();
if (R - L == 1) {
for (int i = 0; i < k; i++) {
LL val = L * k + i;
for (auto to : v[val]) {
ans.mat[i][to.to - (R * k)] = to.w;
}
}
return ans;
}
LL mid = (L + R) / 2;
tran m1 = solve(L, mid);
tran m2 = solve(mid, R);
for (int l = 0; l < k; l++) {
for (int r = 0; r < k; r++) {
for (int m = 0; m < k; m++) {
ans.mat[l][r] = min(ans.mat[l][r], m1.mat[l][m] + m2.mat[m][r]);
}
}
}
return ans;
}
LL a, b, res, b1, b2;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
LL k, n, m, o;
string line;
getline(cin, line);
stringstream ss(line);
ss >> k >> n >> m >> o;
for (int i = 1; i <= m; i++) {
getline(cin, line);
stringstream edge_ss(line);
LL a, b, t;
edge_ss >> a >> b >> t;
v[a].emplace_back(b, t);
}
vector<LL> out;
for (int i = 1; i <= o; i++) {
getline(cin, line);
stringstream query_ss(line);
LL a, b;
query_ss >> a >> b;
int b1 = a / k;
int b2 = b / k;
if (b1 >= b2 || m == 0) {
out.push_back(-1);
}
else {
LL res = solve(b1, b2).mat[a - b1 * k][b - b2 * k];
if (res >= INF) out.push_back(-1);
else out.push_back(res);
}
}
for (LL x : out) {
cout << x << '\n';
}
return 0;
}