Submission #1212658

#TimeUsernameProblemLanguageResultExecution timeMemory
12126583lektraToll (BOI17_toll)C++20
100 / 100
142 ms171920 KiB
#include<bits/stdc++.h> using namespace std; const int maxN = 1e5+1; const int lg = 17; const int inf_set = 0x3f; const int inf_comp = 0x3f3f3f3f; int k; vector<pair<int,int>> graph[maxN]; int dp[maxN][5][lg][5]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t, n, m, a, b, c, d; cin >> k >> n >> m >> t; memset(dp, inf_set, sizeof(dp)); // EDGES for(int i = 0; i < m; ++i){ cin >> a >> b >> d; graph[a].push_back({b,d}); dp[a/k][a%k][0][b%k] = d; } // EXPLORING THE GRAPH for(int i = 1; i < lg; ++i){ for(int deepness = 0; deepness + (1<<i) < (n + k -1)/k; ++deepness){ for(int ini = 0; ini < k; ++ini){ for(int mid = 0; mid < k; ++mid){ for(int fin = 0; fin < k; ++fin){ dp[deepness][ini][i][fin] = min(dp[deepness][ini][i][fin], dp[deepness][ini][i-1][mid] + dp[deepness + (1<<(i-1))][mid][i-1][fin]); } } } } } // QUERIES int queries[k][k]; // New layer, Mod int temp[k][k]; while(t--){ cin >> a >> b; if(a/k >= b/k) cout << -1 << '\n'; else{ memset(queries, inf_set, sizeof(queries)); for(int i = 0; i < k; ++i) queries[i][i] = 0; c = a/k; d = (b/k) - (a/k); // distance from one to another //cout << d << '\n'; for(int i = lg-1; i >= 0; --i){ if(d&(1<<i)){ //cout << i << '\n'; memset(temp, inf_set, sizeof(temp)); for(int ori = 0; ori < k; ++ori){ for(int dest = 0; dest < k; ++dest){ for(int mid = 0; mid < k; ++mid){ temp[ori][dest] = min(temp[ori][dest], queries[ori][mid] + dp[c][mid][i][dest]); } } } memcpy(queries, temp, sizeof(temp)); c += (1<<i); } } if(queries[a%k][b%k] != inf_comp) cout << queries[a%k][b%k] << '\n'; else cout << -1 << '\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...