# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
399544 |
2021-05-06T03:23:43 Z |
Andyvanh1 |
Toll (BOI17_toll) |
C++14 |
|
0 ms |
0 KB |
#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;
}
Compilation message
toll.cpp: In function 'int get(int, int, int, int)':
toll.cpp:16:13: error: 'INT_MAX' was not declared in this scope
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:56:27: note: in expansion of macro 'INF'
56 | part[b] = INF/3;
| ^~~
toll.cpp:5:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
4 | #include <math.h>
+++ |+#include <climits>
5 | using namespace std;
toll.cpp:16:13: error: 'INT_MAX' was not declared in this scope
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:60:40: note: in expansion of macro 'INF'
60 | if(dp[i][c][a][b]!=INF/3){
| ^~~
toll.cpp:16:13: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:60:40: note: in expansion of macro 'INF'
60 | if(dp[i][c][a][b]!=INF/3){
| ^~~
toll.cpp:16:13: error: 'INT_MAX' was not declared in this scope
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:73:16: note: in expansion of macro 'INF'
73 | if(cur[l]==INF/3){
| ^~~
toll.cpp:16:13: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:73:16: note: in expansion of macro 'INF'
73 | if(cur[l]==INF/3){
| ^~~
toll.cpp: In function 'void solve()':
toll.cpp:16:13: error: 'INT_MAX' was not declared in this scope
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:92:38: note: in expansion of macro 'INF'
92 | dp[i][j][f][l] = INF / 3;
| ^~~
toll.cpp:16:13: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
16 | #define INF INT_MAX
| ^~~~~~~
toll.cpp:92:38: note: in expansion of macro 'INF'
92 | dp[i][j][f][l] = INF / 3;
| ^~~