#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> adjlist;
int k,n,num;
int INF = 1e9;
pair<int,int> toCoord(int x){
return {x/k,x%k};
}
vector<vector<int>> combine(vector<vector<int>> &a, vector<vector<int>> &b, int m){
//cout<<m<<endl;
//x - index of rightmost connector
vector<vector<int>> ans(k,vector<int>(k,INF));
for (int i = 0; i<k; i++){
for (int j = 0; j<k; j++){
//get from a[i][_] to b[_][j]
int mindist = INF;
for (int x = 0; x<k; x++){
if (a[i][x]==INF){continue;}
for (auto v : adjlist[m*k+x]){
//cout<<v.first<<" "<<v.second<<endl;
int node = (v.first)%k;
int dist = v.second;
//cout<<node<<endl;
if (b[node][j]==INF){continue;}
mindist=min(mindist,a[i][x]+b[node][j]+dist);
}
}
ans[i][j]=mindist;
}
}
return ans;
}
struct Node{
int s,e,m;
vector<vector<int>> v;
Node *l, *r;
Node(int _s, int _e){
s=_s;e=_e;
if (s==e){
v.resize(k,vector<int>(k,INF));
for (int i = 0; i<k; i++){
v[i][i]=0;
}
return;
}
m = (s+e)/2;
l = new Node(s,m);
r = new Node(m+1,e);
v = combine(l->v,r->v,m);
}
vector<vector<int>> query(int a, int b){
if (a==s&&b==e){
return v;
}
if (b<=m){
return l->query(a,b);
} else if (m<a){
return r->query(a,b);
} else {
return combine(l->query(a,m),r->query(m+1,b),m);
}
}
};
int main(){
//cin.tie(0);
//ios_base::sync_with_stdio(0);
int m,o;
cin>>k>>n>>m>>o;
adjlist.resize(n);
for (int i = 0; i<m; i++){
int a,b,t;
cin>>a>>b>>t;
adjlist[a].push_back({b,t});
}
num=(n+k-1)/k;
Node *root = new Node(0,num-1);
for (int i = 0; i<o; i++){
int a,b;
cin>>a>>b;
if (a==b){
cout<<0<<'\n';
continue;
}
auto ai = toCoord(a);
auto bi = toCoord(b);
if (ai.first>=bi.first){
cout<<-1<<'\n';
continue;
}
auto q = root->query(ai.first,bi.first);
int ans = q[ai.second][bi.second];
if (ans==INF){
cout<<-1<<'\n';
} else {
cout<<ans<<'\n';
}
}
}
Compilation message
toll.cpp: In member function 'std::vector<std::vector<int> > Node::query(int, int)':
toll.cpp:66:27: error: cannot bind non-const lvalue reference of type 'std::vector<std::vector<int> >&' to an rvalue of type 'std::vector<std::vector<int> >'
return combine(l->query(a,m),r->query(m+1,b),m);
~~~~~~~~^~~~~
toll.cpp:12:21: note: initializing argument 1 of 'std::vector<std::vector<int> > combine(std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, int)'
vector<vector<int>> combine(vector<vector<int>> &a, vector<vector<int>> &b, int m){
^~~~~~~
