#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
using namespace std;
int n, m, k, q;
map<pair<pii, pii>, ll> dp;
ll resi(int a, int b, int x, int y)
{
if (dp[{{a, b}, {x, y}}]) return dp[{{a, b}, {x, y}}];
if ((a+1)==b) return 2000000010;
int mid=a+(b-a)/2;
ll ress=2000000010;
for (int i=0; i<k; i++)
{
ress=min(ress, resi(a, mid, x, i)+resi(mid, b, i, y));
}
dp[{{a, b}, {x, y}}]=ress;
return ress;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin>>k>>n>>m>>q;
for (int i=0; i<m; i++)
{
int u, v, t; cin>>u>>v>>t;
dp[{{u/k, v/k}, {u%k, v%k}}]=t;
}
while (q--)
{
int u, v; cin>>u>>v;
int ress=resi(u/k, v/k, u%k, v%k);
if (ress>=2000000010) cout<<-1<<endl;
else cout<<ress<<endl;
}
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:34:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |