#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int N = 1e5 + 1;
int k, n, m, q;
vii a[N];
pii b[N];
void subtask1() {
vi d(n, inf);
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push(pii(0, 0));
d[0] = 0;
while (heap.size()) {
int u = heap.top().se;
ll du = heap.top().fi;
heap.pop();
if (du > d[u]) continue;
for (pii v: a[u]) {
if (d[v.se] > du + v.fi) {
d[v.se] = du + v.fi;
heap.push(pii(d[v.se], v.se));
}
}
}
for (int i = 1; i <= q; i++) {
int x, y;
x = b[i].fi;
y = b[i].se;
if (x > y) {
cout << "-1\n";
continue;
}
cout << d[y] - (x <= 0 ? 0 : d[x - 1]) << '\n';
}
}
const int inf = 1e9;
void subtask2() {
vi d(n, inf);
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push(pii(0, 0));
d[0] = 0;
while (heap.size()) {
int u = heap.top().se;
int du = heap.top().fi;
heap.pop();
if (du > d[u]) continue;
for (pii v: a[u]) {
if (d[v.se] > du + v.fi) {
d[v.se] = du + v.fi;
heap.push(pii(d[v.se], v.se));
}
}
}
for (int i = 1; i <= q; i++) {
cout << (d[b[i].se] == inf ? -1 : d[b[i].se]) << '\n';
}
}
void subtask3() {
for (int i = 1; i <= q; i++) {
int x, y;
x = b[i].fi;
y = b[i].se;
vi d(n, inf);
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push(pii(0, x));
d[x] = 0;
while (heap.size()) {
int u = heap.top().se;
int du = heap.top().fi;
if (u == y) {
cout << d[u] << '\n';
break;
}
heap.pop();
if (du > d[u]) continue;
for (pli v: a[u]) {
if (d[v.se] > du + v.fi) {
d[v.se] = du + v.fi;
heap.push(pii(d[v.se], v.se));
}
}
}
if (d[y] == inf) cout << "-1\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> k >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
a[x].pb(pii(z, y));
}
bool flag = 1;
for (int i = 1; i <= q; i++) {
cin >> b[i].fi >> b[i].se;
if (b[i].fi) flag = 0;
}
if (k == 1) {
subtask1();
return 0;
}
if (flag) {
subtask2();
return 0;
}
subtask3();
return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/
Compilation message
toll.cpp: In function 'void subtask1()':
toll.cpp:16:17: error: 'inf' was not declared in this scope; did you mean 'ynf'?
16 | vi d(n, inf);
| ^~~
| ynf
