線段樹優化建圖

/*

work by:Ariel_

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define int long long

#define lson rt << 1

#define rson rt << 1|1

using namespace std;

const int N = 3e6 + 5, K = 5e5 + 5;

int read() {

 int x = 0, f = 1; char c = getchar();

 while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}

 while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

 return x * f;

}

int n, m, s, opt, a[N];

struct edge{int v, nxt, w;}e[N];

int head[N], E;

void add_edge(int u, int v, int w) {

 e[++E] = (edge) {v, head[u], w};

 head[u] = E;

}

namespace Seg{

 void build(int rt, int l, int r) {

 if (l == r) {a[l] = rt; return;}

 int mid = (l + r) >> 1;

 add_edge(rt, rt << 1, 0), add_edge(rt, rt << 1 | 1, 0);

 add_edge((rt << 1) + K, rt + K, 0), add_edge((rt << 1 | 1) + K, rt + K, 0);

 build(lson, l, mid), build(rson, mid + 1, r);

 }

 void modify(int rt, int l, int r, int L, int R, int v, int w) {

 if (L <= l && r <= R) {

 if (opt == 2) add_edge(v + K, rt, w);

 else add_edge(rt + K, v, w);

 return;

 }

 int mid = (l + r) >> 1;

 if (L <= mid) modify(lson, l, mid, L, R, v, w);

 if (R > mid) modify(rson, mid + 1, r, L, R, v, w);

 }

}

using namespace Seg;

priority_queue<pair<int, int> > q;

int dis[N], vis[N];

void dij(int s) {

 memset(dis, 0x3f, sizeof dis), dis[s] = 0;

 q.push(make_pair(0, s));

 while(q.size()) {

 int u = q.top().second; q.pop();

 if (vis[u]) continue;

 vis[u] = 1;

 for (int i = head[u]; i; i = e[i].nxt) {

 int v = e[i].v;

 if (e[i].w + dis[u] < dis[v]) {

 dis[v] = e[i].w + dis[u];

 q.push(make_pair(-dis[v], v));//默認從小到大排序，所以要取負號

 }

 }

 }

}

signed main(){

 n = read(), m = read(), s = read();

 build(1, 1, n);

 for (int i = 1; i <= n; i++) add_edge(a[i], a[i] + K, 0), add_edge(a[i] + K, a[i], 0);

 for (int i = 1, x, y, z, l, r, w; i <= m; i++) {

 opt = read();

 if (opt == 1) {

 x = read(), y = read(), z = read();//這裏的 x, y 對應線段樹的第幾個葉子節點，a[x] 存的是線段樹中第 x 葉子節點的標號

 add_edge(a[x] + K, a[y], z);

 }

 else {

 x = read(), l = read(), r = read(), w = read();

 modify(1, 1, n, l, r, a[x], w);

 }

 }

 dij(a[s] + K);

 for (int i = 1; i <= n; i++)

 printf("%lld%c",dis[a[i]]!=0x3f3f3f3f3f3f3f3fll?dis[a[i]]:-1,i==n?'\n':' ');

 puts("");

 return 0;

}




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.
80.
81.
82.
83.
84.