Submission #495518

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
4955182021-12-19 08:39:57hoanghq2004Toll (BOI17_toll)C++14
100 / 100
219 ms199344 KiB
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 10;
int len, n, m, q;
int f[Nmax][5][5][20];
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> len >> n >> m >> q;
memset(f, 60, sizeof(f));
while (m--) {
int u, v, w;
cin >> u >> v >> w;
f[u / len][u % len][v % len][0] = min(f[u / len][u % len][v % len][0], w);
}
for (int lg = 1; (1 << lg) <= n / len + 1; ++lg) {
for (int i = 0; i + (1 << lg) - 1 <= n / len + 1; ++i) {
for (int x = 0; x < len; ++x)
for (int y = 0; y < len; ++y) {
for (int z = 0; z < len; ++z) {
f[i][x][y][lg] = min(f[i][x][y][lg], f[i][x][z][lg - 1] + f[i + (1 << lg - 1)][z][y][lg - 1]);
}
}
}
}
while (q--) {
int a, b;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:24:98: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |                         f[i][x][y][lg] = min(f[i][x][y][lg], f[i][x][z][lg - 1] + f[i + (1 << lg - 1)][z][y][lg - 1]);
      |                                                                                               ~~~^~~
#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...