题面描述
支持区间向单点连边的单源最短路问题。
题解
线段树优化建图模板题，建立两个线段树，一个由内向外连，一个由外向内连即可，具体细节就按照线段树区间操作口胡一下就好了
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
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 3e6+5;
struct Edge
{
int next, to, w;
Edge(int next = 0, int to = 0, int w = 0):next(next), to(to), w(w) {};
}edge[N];
int tot, head[N];
void add(int x, int y, int z) { edge[++tot] = Edge(head[x], y, z); head[x] = tot; }
int n, m, q, s;
int64 d[N];
int in[N], out[N];
void build(int x, int l, int r)
{
if(l == r) return void(in[x] = out[x] = l);
int mid = (l+r)>>1; in[x] = ++m; out[x] = ++m;
build(x<<1, l, mid); build(x<<1|1, mid+1, r);
add(in[x], in[x<<1], 0); add(in[x], in[x<<1|1], 0);
add(out[x<<1], out[x], 0); add(out[x<<1|1], out[x], 0);
}
void outUpdate(int x, int l, int r, int ql, int qr, int d, int w)
{
if(ql <= l&&r <= qr) return add(out[x], d, w);
int mid = (l+r)>>1;
if(ql <= mid) outUpdate(x<<1, l, mid, ql, qr, d, w);
if(qr > mid) outUpdate(x<<1|1, mid+1, r, ql, qr, d, w);
}
void inUpdate(int x, int l, int r, int ql, int qr, int d, int w)
{
if(ql <= l&&r <= qr) return add(d, in[x], w);
int mid = (l+r)>>1;
if(ql <= mid) inUpdate(x<<1, l, mid, ql, qr, d, w);
if(qr > mid) inUpdate(x<<1|1, mid+1, r, ql, qr, d, w);
}
int main()
{
n = read(), q = read(), s = read(); m = n;
build(1, 1, n);
for(int i = 1; i <= q; ++i)
{
int op = read(), v = read(), u, l, r, w;
if(op == 1) u = read(), w = read(), add(v, u, w);
else if(op == 2) l = read(), r = read(), w = read(), inUpdate(1, 1, n, l, r, v, w);
else l = read(), r = read(), w = read(), outUpdate(1, 1, n, l, r, v, w);
}
memset(d, 0x3f, sizeof(d)); d[s] = 0;
priority_queue<pair<int64, int> > q; q.push(make_pair(0, s));
while(q.size())
{
int x = q.top().second;
int64 dx = -q.top().first; q.pop();
if(dx != d[x]) continue;
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to, z = edge[i].w;
if(d[y] > d[x]+z) d[y] = d[x]+z, q.push(make_pair(-d[y], y));
}
}
for(int x = 1; x <= n; ++x) printf("%lld ", d[x]^d[0]?d[x]:-1);
return 0;
}