제출 #1172297

#제출 시각아이디문제언어결과실행 시간메모리
1172297DanielPr8Toll (BOI17_toll)C++20
100 / 100
143 ms74308 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector<ll>; using vvl = vector<vll>; using pll = pair<ll,ll>; using vpl = vector<pll>; using vvp = vector<vpl>; #define f fisrt #define s second #define pb push_back #define all(v) v.begin(),v.end() int main(){ ios_base::sync_with_stdio(0);cin.tie(NULL); ll k, n, m, o, f=20, a, b, t; cin >> k >> n >> m >> o; n+=k-n%k; vector<vvl> ed(f, vvl(n, vll(k, 1e11))); for(ll i = 0; i < m; ++i){ cin >> a >> b >> t; ed[0][a][b%k]=t; } for(ll h = 1; h < f; ++h){ for(ll i = 0; i < n; ++i){ for(ll j = 0; j < k; ++j){ for(ll p = 0; p < k; ++p){ ll l = i-i%k+(1<<(h-1))*k+p; if(l<n)ed[h][i][j] = min(ed[h][i][j], ed[h-1][i][p] + ed[h-1][l][j]); } } } } while(o--){ vll dis(k, 1e11), dis2; cin >> a >> b; t = b/k-a/k; dis[a%k]=0; a-=a%k; for(ll h = f-1; h >= 0; --h){ if((1<<h)<=t){ dis2 = vll(k, 1e11); for(ll i = 0; i < k; ++i){ for(ll j = 0; j < k; ++j){ dis2[i] = min(dis2[i],dis[j]+ed[h][a+j][i]); } } t-=(1<<h); a+=(1<<h)*k; swap(dis, dis2); } } if(dis[b%k]<1e11)cout << dis[b%k] << "\n"; else cout << "-1\n"; } }
#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...