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
78
79
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
constexpr int MX = 1e5+5;
int N, K;
struct ticket_t {
int c, p, a, b;
} T[MX];
struct seg_tree {
int seg[4*MX];
inline int pull(const int & a, const int & b) { return max(a, b); }
void build(int l = 0, int r = MX-1, int n = 1) {
if (l == r) { seg[n] = T[l].b; return; }
int m = l+r>>1;
build(l, m, n<<1), build(m+1, r, n<<1|1);
seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
void remove(vector<int> & vc, int x, int l = 0, int r = MX-1, int n = 1) {
if (l >= K || T[l].a > x || seg[n] < x) return;
if (l == r) {
seg[n] = -1, vc.push_back(l);
}
else {
int m = l+r>>1;
remove(vc, x, l, m, n<<1), remove(vc, x, m+1, r, n<<1|1);
seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
}
};
void dijkstra(vector<ll> & dist) {
priority_queue<pl, vector<pl>, greater<>> pq;
for (int i = N; i < N+K; ++i)
dist[T[i-N].c] = min(dist[i]+T[i-N].p, dist[T[i-N].c]);
for (int i = 0; i < N; ++i) if (dist[i] < 1e18)
pq.emplace(dist[i], i);
seg_tree seg;
seg.build();
while (pq.size()) {
ll d = pq.top().f, u = pq.top().s;
pq.pop();
if (d > dist[u]) continue;
vector<int> vc;
seg.remove(vc, u);
for (int v : vc) {
if (dist[v+N] > d) {
dist[v+N] = d;
if (dist[T[v].c] > d+T[v].p)
dist[T[v].c] = d+T[v].p,
pq.emplace(dist[T[v].c], T[v].c);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> K;
for (int i = 0; i < K; ++i) {
cin >> T[i].c >> T[i].p >> T[i].a >> T[i].b;
--T[i].c, --T[i].a, --T[i].b;
}
sort(T, T+K, [](auto & a, auto & b) { return a.a < b.a; });
vector<ll> L(N+K, 1e18), R(N+K, 1e18), D(N+K);
L[0] = R[N-1] = 0;
dijkstra(L), dijkstra(R);
for (int i = 0; i < N+K; ++i) D[i] = L[i]+R[i];
dijkstra(D);
for (int i = 0; i < N; ++i)
cout << (D[i] < 1e18 ? D[i] : -1) << '\n';
}
|
