线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
typedef std::pair<int,int> node;
const int _=2e5+1,inf=0x7f7f7f7f;
int n,m,s,fp,hed[_],nxt[_],ver[_],edg[_],d[_];
namespace sgt {
struct node {
int l,r,val,pos;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define val(x) tree[x].val
#define pos(x) tree[x].pos
}tree[1<<19];
void build(int p,int l,int r) {
l(p)=l;r(p)=r;
if(l+1==r) {
val(p)=inf,pos(p)=l;if(l==s) val(p)=0;
} else {
int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid,r);
if(val(p<<1)<=val(p<<1|1))
val(p)=val(p<<1),pos(p)=pos(p<<1);
else val(p)=val(p<<1|1),pos(p)=pos(p<<1|1);
}
}
void modify(int p,int d,int v) {
if(l(p)+1==r(p)) val(p)=v;
else{
if(d<r(p<<1)) modify(p<<1,d,v);
else modify(p<<1|1,d,v);
if(val(p<<1)<=val(p<<1|1))
val(p)=val(p<<1),pos(p)=pos(p<<1);
else val(p)=val(p<<1|1),pos(p)=pos(p<<1|1);
}
}
}
int read() {
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
return x;
}
void link(int u,int v,int w) {
ver[++fp]=v;edg[fp]=w;nxt[fp]=hed[u];hed[u]=fp;
}
void dijkstra() {
memset(d,0x7f,sizeof(d));d[s]=0;
int u,v,w;sgt::build(1,1,n+1);
while(sgt::val(1)^inf){
u=sgt::pos(1);sgt::modify(1,u,inf);
for(int i=hed[u];i;i=nxt[i]){
v=ver[i],w=edg[i];
if(d[u]+w<d[v]) sgt::modify(1,v,d[v]=d[u]+w);
}
}
}
int main() {
n=read(),m=read(),s=read();
for(int i=0,u,v,w;i<m;++i) u=read(),v=read(),w=read(),link(u,v,w);
dijkstra();
for(int i=1;i<=n;++i) printf("%d ",d[i]);
return 0;
}

Download

priority_queue 不吸氧气跑某模板需要 800ms,用线段树优化只要不到 400ms。不过代码量太大,没有什么实践意义。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 算法

评论

您需要成为穿墙的邪仙以加载 Disqus。