| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 399544 | Andyvanh1 | Toll (BOI17_toll) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define vt vector
#define pb push_back
typedef long long ll;
typedef vt<int> vi;
#define INF INT_MAX
int N,M,K;
vt<vt<vt<vi>>> dp;
vt<vi> arr;
vt<vt<pair<int,int>>> adjlist;
void gen(){
for(int f = 1; f < 17; f++){
for(int i = 0; i < N; i++){
for(int j = 0; j < K; j++){
for(int l = 0; l < K; l++ ){
if(i+(1<<(f-1))<N) {
for(int a = 0; a < K; a++){
dp[i][j][f][l] = min(dp[i][j][f][l],dp[i][j][f - 1][a] + dp[i + (1 << (f - 1))][a][f - 1][l]);
}
}
}
}
}
}
}
int get(int i, int j, int f, int l){
vi cur(K);
f--;
for(int a = 0; a < K; a++){
cur[a] = dp[i][j][0][a];
}
i++;
for(int a = 0; a < 17; a++){
if((1<<a)&f){
vi part(K);
for(int b = 0; b < K; b++){
part[b] = INF/3;
}
for(int b = 0; b < K; b++){
for(int c = 0; c < K; c++){
if(dp[i][c][a][b]!=INF/3){
part[b] = min(part[b],cur[c]+dp[i][c][a][b]);
}
}
}
i+=(1<<a);
for(int b = 0; b < K; b++){
cur[b] = part[b];
}
}
}
if(cur[l]==INF/3){
return -1;
}
return cur[l];
}
void solve(){
int m, n, o;
cin>>K>>n>>m>>o;
N = (n-1)/K+1;
arr.resize(N,vi(K));
adjlist.resize(n);
dp.resize(N,vt<vt<vi>>(K,vt<vi>(17,vi(K))));
for(int i = 0; i < N; i++){
for(int j = 0; j < K; j++){
for(int l = 0; l < K; l++){
for(int f = 0; f < 17; f++) {
dp[i][j][f][l] = INF / 3;
}
}
}
}
for(int i = 0; i < m; i++){
int u,v,w;
cin>>u>>v>>w;
dp[u/K][u%K][0][v%K] = w;
}
gen();
for(int i = 0; i < o; i++){
int u,v;
cin>>u>>v;
cout<<get(u/K,u%K,(v/K-u/K),v%K)<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin>>t;
for(int i = 0; i < t; i++){
solve();
}
return 0;
}