| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1251738 | akksss | Toll (BOI17_toll) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
// For Ordered Set
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// For snippet use pbds
*/
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define dbg(...) 42
#endif
#define pi 3.141592653589793238
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define int long long
ll M = 1000000007;
// Solution Starts Here.....
const int NN = 5e4+5;
const int KK = 5;
const int Log = 25;
int dp[NN][KK][Log];
void solve(){
int K, n, m, O;
cin >> K >> n >> m >> O;
vector<int> adj[n];
map<pair<int,int>,int> wt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < K; j++) {
for (int k = 0; k < Log; k++) {
dp[i][j][k] = 1e14;
}
}
}
for (int i = 0; i < m; i++) {
int a, b, t; cin >>a >> b >> t;
wt[{a, b}] = t;
dp[a][b%K][0] = t;
}
for (int j = 1; j < Log; j++) {
for (int i = 0; i < n; i++) {
for (int k = 0; k < K; k++) {
int nxt = i/K + (1<<j) + k;
if(nxt>=n) continue;
// update dp[i][j][k]
nxt = i/K + (1<<(j-1));
for (int k1 = 0; k1 <K; k1++) {
int val1 = dp[i][k1][j-1];
int val2 = dp[K*nxt+k1][k][j-1];
dp[i][k][j] = min(dp[i][k][j],val1 + val2);
}
}
}
}
vector<int> id;
function<int(int,int)> query = [&](int a, int b){
if(a == b) return 0ll;
if(a >= n) return 0ll;
int val = 1e14;
if(a/K >= b/K) return val;
int ans = 1e14;
int i = id.back();
// dbg(i);
id.pop_back();
dbg(i, id);
for (int j = 0; j < K; j++) {
// dbg(dp[a][j][i], j);
ans = min(ans, dp[a][j][i] + query( (a/K + (1<<i))*K + j, b));
dbg(ans);
}
return ans;
};
// O = 1;
while(O--){
int a, b; cin >> a >> b;
dbg(a, b);
id.clear();
if(a/K >= b/K){
cout << "-1\n";
continue;
}
if(a == b){
cout << "0\n";
continue;
}
int dist = b/K - a/K;
for (int i=Log-1; i >= 0; i--){
if(dist&(1<<i)) id.push_back(i);
}
dbg(dist, id);
int ans = query(a, b);
if(ans == 1e14){
cout << "-1\n";
}
else cout << ans << "\n";
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1;
// cin >> TET;
for (int i = 1; i <= TET; i++)
{
solve();
}
}