# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
828264 |
2023-08-17T07:29:10 Z |
Darren0724 |
Toll (BOI17_toll) |
C++17 |
|
1 ms |
724 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=55;
const int INF=1e9;
const int K=__lg(N)+1;
vector jump(N, vector (K,vector(5,vector(5,INF))));
void f(vector<vector<int>> &a,vector<vector<int>> &b,vector<vector<int>> &c,int k){
//i -> p -> j
for(int i=0;i<k;i++){
for(int p=0;p<k;p++){
for(int j=0;j<k;j++){
c[i][j]=min(c[i][j],a[i][p]+b[p][j]);
}
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int k,n,m,q;cin>>k>>n>>m>>q;
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
int t=a/k;
jump[t][0][a%k][b%k]=c;
}
for(int j=1;j<K;j++){
for(int i=0;i+(1<<j-1)<N;i++){
f(jump[i][j-1],jump[i+(1<<j-1)][j-1],jump[i][j],k);
}
}
for(int i=0;i<q;i++){
vector ans(5,vector(5,0ll));
int a,b;cin>>a>>b;
int t=(b/k)-(a/k);
if(t==0){
cout<<-1<<endl;
continue;
}
int now=a/k;
for(int j=0;j<K;j++){
if(t&(1<<j)){
vector<vector<int>> y(5);
for(int j1=0;j1<5;j1++){
y[j1]=ans[j1];
ans[j1].assign(5,INF);
}
f(y,jump[now][j],ans,k);
now+=(1<<j);
}
}
int ans1=ans[a%k][b%k];
cout<<(ans1>=INF?-1:ans1)<<endl;
}
return 0;
}
Compilation message
toll.cpp: In function 'int32_t main()':
toll.cpp:29:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
29 | for(int i=0;i+(1<<j-1)<N;i++){
| ~^~
toll.cpp:30:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
30 | f(jump[i][j-1],jump[i+(1<<j-1)][j-1],jump[i][j],k);
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
720 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
720 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |