제출 #1184986

#제출 시각아이디문제언어결과실행 시간메모리
1184986lalig777Toll (BOI17_toll)C++20
100 / 100
241 ms73312 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; typedef long long int ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef vector<vvvll> vvvvll; int K, N, M, O; int levs; vvvvll dp; ll func(int levi, int i, int k, int j, int l){ if (levi+(1<<k)>=levs) return 1e18; return dp[levi][i][k][l]+dp[levi+(1<<k)][l][k][j]; } void ini(){ for (int k=1; k<20; k++){ for (int levi=0; levi<levs-1; levi++){ for (int i=0; i<K; i++){ for (int j=0; j<K; j++){ for (int l=0; l<K; l++){ dp[levi][i][k][j]=min(dp[levi][i][k][j], func(levi,i,k-1,j,l)); } } } } }return; } ll binlift(int a, int b){ int act=a/K, fin=b/K; if(act==fin){ if (a==b) return 0; else return -1; } vector<ll>res(K, 1e18); res[a%K]=0; for (int k=19; k>=0; k--){ if (act+(1<<k)<fin){ vector<ll>aux(K, 1e18); for (int i=0; i<K; i++){ for (int j=0; j<K; j++) aux[i]=min(aux[i], res[j]+dp[act][j][k][i]); }swap(res, aux); act=act+(1<<k); } } ll ans=1e18; for (int i=0; i<K; i++) ans=min(ans, res[i]+dp[act][i][0][b%K]); if (ans==1e18) return -1; else return ans; } int main(){ cin>>K>>N>>M>>O; levs=ceil(N/K); dp.assign(levs, vvvll(K, vvll(20, vll(K, 1e18)))); for (int i=0; i<M; i++){ int a, b; ll t; cin>>a>>b>>t; dp[a/K][a%K][0][b%K]=t; } ini(); while (O--){ int a, b; cin>>a>>b; cout<<binlift(a, b)<<'\n'; } return 0; }
#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...