听说 zkw 线段树优化 dijkstra 跑得很快呢，洛谷最优解都是用这个的。
然后我就自己打了一发。
确实快了许多，但还是被最优解吊着打……
但至少能过bzoj3040。
把普通堆优 dij 的堆改成线段树就可以了。
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
| struct Edge
{
int to, dist, nxt;
} e[maxm << 1];
int first[maxn];
inline void add_edge(int from, int to, int dist)
{
static int cnt = 0;
e[++cnt].nxt = first[from];
first[from] = cnt;
e[cnt].dist = dist;
e[cnt].to = to;
}
int dist[maxn];
struct DIJKSTRA
{
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
struct Tree
{
int no[maxn << 2];
int t;
inline void build_tree()
{
for(t = 1; t <= n; t <<= 1);
for(register int i = 1; i <= n; ++i)
no[i + t] = i;
}
inline void change(int k)
{
for(k += t, k >>= 1; k; k >>= 1)
no[k] = dist[no[ls(k)]] < dist[no[rs(k)]]
? no[ls(k)] : no[rs(k)];
}
inline void del(int k)
{
for(no[k += t] = 0, k >>= 1; k; k >>= 1)
no[k] = dist[no[ls(k)]] < dist[no[rs(k)]]
? no[ls(k)] : no[rs(k)];
}
} tr;
inline void dijkstra(int s)
{
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
tr.build_tree();
tr.change(s);
for(int i = 1; i <= n; ++i)
{
register int now = tr.no[1];
if(!now || dist[now] >= inf)
break;
tr.del(now);
for(int j = first[now]; j; j = e[j].nxt)
{
register int to = e[j].to;
if(dist[to] > dist[now] + e[j].dist)
{
dist[to] = dist[now] + e[j].dist;
tr.change(to);
}
}
}
}
}
|
