#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
int K,N,M,O;
cin>>K>>N>>M>>O;
vector<vector<int>> dist(N, vector<int>(N, INF));
for (int i = 0; i < N; ++i)
dist[i][i] = 0;
for (int i = 0; i < M; ++i) {
int a, b, c;
cin >> a >> b >> c;
int u=a/K;
int v=b/K;
if(v==u+1)dist[a][b] = c;
}
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (dist[i][k] < INF && dist[k][j] < INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int a,b;
while(O--){
cin>>a>>b;
if(dist[a][b]==INF){
cout<<-1<<endl;
}else{
cout<<dist[a][b]<<endl;
}
}
return 0;
}
# | 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... |