Submission #568301

#TimeUsernameProblemLanguageResultExecution timeMemory
568301inluminasToll (BOI17_toll)C++17
100 / 100
199 ms169956 KiB
#include"bits/stdc++.h" using namespace std; #define ll long long #define endl "\n" #define fastio ios_base::sync_with_stdio(false) #define inf LLONG_MAX #define l first #define r second const int lmt=50001; ll dp[lmt][17][5][5]; int main(){ fastio; for(int i=0;i<lmt;i++){ for(int j=0;j<17;j++){ for(int k=0;k<5;k++){ for(int l=0;l<5;l++) dp[i][j][k][l]=1e15; } } } int k,n,m,q; cin>>k>>n>>m>>q; for(int i=1;i<=m;i++){ ll u,v,t; cin>>u>>v>>t; dp[u/k][0][u%k][v%k]=min(dp[u/k][0][u%k][v%k],t); } for(int mv=1;mv<17;mv++){ for(int i=0;i<=(n-1)/k;i++){ for(int j=0;j<k;j++){ for(int l=0;l<k;l++){ for(int o=0;o<k;o++){ int b=i+(1<<(mv-1)); if(b>(n-1)/k) continue; dp[i][mv][j][l]=min(dp[i][mv][j][l],dp[i][mv-1][j][o]+dp[b][mv-1][o][l]); } } } } } /*for(int i=0;i<=(n-1)/k;i++){ for(int j=0;j<k;j++){ for(int l=0;l<k;l++){ for(int mv=0;mv<2;mv++){ if(dp[i][mv][j][l]==1e15) continue; cout<<dp[i][mv][j][l]<<" "<<i<<" "<<mv<<" "<<j<<" "<<l<<endl; } } } }*/ while(q--){ int u,v; cin>>u>>v; int pre=u/k; ll val[k]; for(int i=0;i<k;i++) val[i]=1e15; val[u%k]=0; int dis=v/k-u/k; for(int j=16;j>=0;j--){ int b=pre+(1<<j); if(b>v/k || dis<(1<<j)) continue; dis-=(1<<j); ll val2[k]; for(int i=0;i<k;i++) val2[i]=1e15; for(int i=0;i<k;i++){ for(int l=0;l<k;l++){ val2[i]=min(val2[i],val[l]+dp[pre][j][l][i]); } } for(int i=0;i<k;i++) val[i]=val2[i]; pre=b; } ll ans=val[v%k]; cout<<(ans==1e15?-1:ans)<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...