This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 5e4 + 5;
int lim = 5;
struct Node
{
int a[5][5];
Node()
{
for(int i = 0; i < lim; i++)
{
for(int j = 0; j < lim; j++)
{
if(i == j)
{
a[i][j] = INF;
}
else
{
a[i][j] = INF;
}
}
}
}
};
void Print(Node X)
{
for(int i = 0; i < lim; i++)
{
for(int j = 0; j < lim; j++)
{
cout << X.a[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
}
Node Merge(Node A, Node B)
{
Node C;
for(int i = 0; i < lim; i++)
{
for(int j = 0; j < lim; j++)
{
for(int k = 0; k < lim; k++)
{
C.a[i][j] = min(C.a[i][j], A.a[i][k] + B.a[k][j]);
}
}
}
return C;
}
int n, q, m;
Node Block[MAXN];
Node IT[4 * MAXN];
void Build(int node, int l, int r)
{
if(l == r)
{
IT[node] = Block[l];
return;
}
int mid = (l + r) >> 1;
Build(node << 1, l, mid);
Build(node << 1 | 1, mid + 1, r);
IT[node] = Merge(IT[node << 1], IT[node << 1 | 1]);
}
Node Get(int node, int l, int r, int L, int R)
{
if(l > R or r < L or L > R)
{
Node tmp;
for(int i = 0; i < lim; i++)
{
tmp.a[i][i] = 0;
}
return tmp;
}
if(L <= l and r <= R)
{
return IT[node];
}
int mid = (l + r) >> 1;
return Merge(Get(node << 1, l, mid, L, R), Get(node << 1 | 1, mid + 1, r, L, R));
}
int main()
{
// freopen("Input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lim >> n >> m >> q;
for(int i = 1; i <= m; i++)
{
int u, v, c;
cin >> u >> v >> c;
Block[u / lim].a[u % lim][v % lim] = min(Block[u / lim].a[u % lim][v % lim], c);
}
int tmp = n / lim;
Build(1, 0, tmp);
while(q--)
{
int x, y;
cin >> x >> y;
if(x / lim > y / lim - 1)
{
cout << -1 << '\n';
continue;
}
Node tt = Get(1, 0, tmp, x / lim, y / lim - 1);
if(tt.a[x % lim][y % lim] == INF)
{
tt.a[x % lim][y % lim] = -1;
}
cout << tt.a[x % lim][y % lim] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |