1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using i64 = long long;
template <typename T>
using vec = std::vector<T>;
template <typename K, typename V>
using umap = __gnu_pbds::gp_hash_table<K, V>;
template <typename T>
using lqueue = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int N = 3e5 + 5;
constexpr i64 INF = 2e18;
int c, n, m, k, deg[N];
i64 v[N], w[N];
vec<std::tuple<int, i64>> G[N];
umap<int, i64> dis[N];
i64 ans[N];
int main() {
#ifdef ONLINE_JUDGE
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
#endif
std::cin >> c >> n >> m >> k;
for (int i = 1; i <= k - 1; i++) std::cin >> v[i], v[i] += v[i - 1];
for (int i = 2; i <= k; i++) std::cin >> w[i], w[i] += w[i - 1];
for (int u = 1; u <= n; u++) {
std::cin >> deg[u];
for (int i = 0, y, z; i < deg[u]; i++) {
std::cin >> y >> z;
G[u].emplace_back(y, z);
}
ans[u] = INF;
}
lqueue<std::tuple<i64, int, int>> pq;
dis[1][1] = 0;
ans[1] = 0;
pq.push({0, 1, 1});
while (!pq.empty()) {
auto [D, p, u] = pq.top();
pq.pop();
if (dis[u][p] != D) continue;
if (p <= deg[u]) {
auto [to, z] = G[u][p - 1];
if (dis[to].find(p) == dis[to].end() || D + z < dis[to][p]) {
dis[to][p] = D + z;
ans[to] = std::min(ans[to], dis[to][p]);
pq.push({D + z, p, to});
}
}
for (int i = 1; i <= std::min(deg[u], k); i++) {
i64 cost = 0;
if (i < p) cost = w[p] - w[i];
else cost = v[i - 1] - v[p - 1];
if (dis[u].find(i) == dis[u].end() || D + cost < dis[u][i]) {
dis[u][i] = D + cost;
ans[u] = std::min(ans[u], dis[u][i]);
pq.push({D + cost, i, u});
}
}
}
for (int i = 1; i <= n; i++) { std::cout << (ans[i] == INF ? -1 : ans[i]) << " "; }
std::cout << "\n";
}
|