Submission #1128862

#TimeUsernameProblemLanguageResultExecution timeMemory
1128862pcheloveksToll (BOI17_toll)C++20
39 / 100
3094 ms5988 KiB
#pragma GCC optimize("O3") #include <iostream> #include <vector> #include <map> #include <set> #include <fstream> #include <algorithm> #include <cstring> // Для memset #define endl '\n' using namespace std; typedef long long LL; typedef pair<LL, LL> pii; const LL DIM = 50007; const LL INF = 999999999999; LL n, k, o, m; class edge { public: LL to, w; }; vector < edge > v[DIM]; class tran { public: LL mat[5][5]; void init() { for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { mat[i][j] = INF; } } } }; tran solve(LL L, LL R) { tran ans; ans.init(); if (R - L == 1) { for (int i = 0; i < k; i++) { LL val = (L - 1) * k + i; for (auto to : v[val]) { ans.mat[i][to.to - ((R - 1) * k)] = to.w; } } return ans; } LL mid = (L + R) / 2; tran m1 = solve(L, mid); tran m2 = solve(mid, R); for (int l = 0; l < k; l++) { for (int r = 0; r < k; r++) { for (int m = 0; m < k; m++) { ans.mat[l][r] = min(ans.mat[l][r], m1.mat[l][m] + m2.mat[m][r]); } } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> n >> m >> o; for (int i = 1; i <= m; i++) { LL a, b, t; cin >> a >> b >> t; v[a].push_back({ b, t }); } for (int i = 1; i <= o; i++) { LL a, b; cin >> a >> b; LL b1 = a / k + 1; LL b2 = b / k + 1; if (b1 >= b2) cout << -1 << endl; else { LL res = solve(b1, b2).mat[a - ((b1 - 1) * k)][b - ((b2 - 1) * k)]; if (res >= INF) cout << -1; else cout << res; cout << endl; } } 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...