单源最短路

对于一张有向图(无向图),求某一点到所有点的最短路长度,有个已经写烂了的算法……

连我这种蒟蒻,这个算法都是烂熟于心了,可见这个算法在OI中影响之大……

没错,这个算法就是已经被写烂了的SPFA……

靠着这个简单的算法,可以通过洛谷之前的

P3371 【模板】单源最短路径

貌似SPFA也就十几行,分分钟AC的那种。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

typedef long long LL;

using std::queue;

const int inf=0x7fffffff;

class GetLenth
{
private:
int PotNum;

typedef struct EdgeNode
{
int to,val;
EdgeNode *next;

EdgeNode(int v,EdgeNode *nxt,int w):to(v),val(w)
{
next=nxt;
}
~EdgeNode()
{
if(next!=NULL)
delete next;
}
}*Edge;

Edge *head=NULL;

inline void add(int u,int v,int w)
{
head[u]=new EdgeNode(v,head[u],w);
//head[v]=new EdgeNode(u,head[v],w);
}

int *dis;
bool *flag;

void SPFA(int s)
{
dis[s]=0;
queue<int> que;
que.push(s);
flag[s]=1;
while(!que.empty())
{
int from=que.front();
que.pop();
flag[from]=0;
for(Edge node=head[from];node;node=node->next)
{
int to=node->to;
if(dis[to]>dis[from]+node->val)
{
dis[to]=dis[from]+node->val;
if(!flag[to])
{
que.push(to);
flag[to]=1;
}
}
}
}
}

public:
GetLenth(int n):PotNum(n)
{
head=new Edge[n+10];
dis=new int[n+10];
for(int i=1;i<=n;i++)
dis[i]=inf;
flag=new bool[n+10];
std::memset(head,0,(n+10)*sizeof(Edge));
std::memset(flag,0,(n+10)*sizeof(bool));
}

~GetLenth()
{
delete [] head;
delete [] dis;
delete [] flag;
}

void input_edge(int m)
{
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
}

void Get(int s)
{
SPFA(s);
for(int i=1;i<=PotNum;i++)
printf("%d ",dis[i]);
puts("");
}
};

int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
GetLenth *get_lenth=new GetLenth(n);
get_lenth->input_edge(m);
get_lenth->Get(s);
delete get_lenth;
return 0;
}

然而,2018年某场比赛之后……

嗯没错,就是NOI

2018年7月19日许多同学在NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路……

然后

惨惨!

SPFA生前是个体面算法,给SPFA上柱香qwq

第一题直接100变60(我这种蒟蒻可能连60都没有)qwq

对于SPFA来说,最坏复杂度是$O(MN)$的,不过大部分情况比这个优,大概是$O(kE)$,不过k大小是玄学,也就是说,搞一个极端数据,比如一张网格图,SPFA就TLE了……

NOI之后,洛谷的 P3371 【模板】单源最短路径变成了P3371 【模板】单源最短路径(弱化版)同时也增加了P4779 【模板】单源最短路径 (标准版)

于是乎,得用稳定的Dijkstra了!

Dijkstra可以说是目前生活中运用最广泛的最短路算法了。

例如,网络层的重要功能就是路由和转发。而路由是根据路由器根据所维护的路由表进行路由选择。所以,如果创建和更新转发表就是一个很重要的问题。通常,在路由时,我们总是选取所需代价最小的一条路由。这里就用到了Dijkstra算法。

那么朴素的Dijkstra算法的复杂度是多少呢?$O(n^2)$很显然不满足需求,甚至不如SPFA。

所以,要使用堆优化……复杂度为$O(n \log n)$

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

typedef long long LL;

using std::priority_queue;

const int inf=0x7fffffff;

class GetLenth
{
private:
int PotNum;

typedef struct EdgeNode
{
int to,val;
EdgeNode *next;

EdgeNode(int v,EdgeNode *nxt,int w):to(v),val(w)
{
next=nxt;
}
~EdgeNode()
{
if(next!=NULL)
delete next;
}
}*Edge;

Edge *head=NULL;

inline void add(int u,int v,int w)
{
head[u]=new EdgeNode(v,head[u],w);
//head[v]=new EdgeNode(u,head[v],w);
}

int *dis;

struct Point
{
int pot,dis;
bool operator <(const Point& tmp) const
{
return this->dis>tmp.dis;
}
};

void Dijkstra(int s)
{
dis[s]=0;
priority_queue<Point> que;
que.push((Point){s,0});
while(!que.empty())
{
Point fr=que.top();
que.pop();
int from=fr.pot;
if(fr.dis==dis[from])
for(Edge node=head[from];node;node=node->next)
{
int to=node->to;
if(dis[to]>dis[from]+node->val)
{
dis[to]=dis[from]+node->val;
que.push((Point){to,dis[to]});
}
}
}
}

public:
GetLenth(int n):PotNum(n)
{
head=new Edge[n+10];
dis=new int[n+10];
for(int i=1;i<=n;i++)
dis[i]=inf;
std::memset(head,0,(n+10)*sizeof(Edge));
}

~GetLenth()
{
delete [] head;
delete [] dis;
}

void input_edge(int m)
{
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
}

void Get(int s)
{
Dijkstra(s);
for(int i=1;i<=PotNum;i++)
printf("%d ",dis[i]);
puts("");
}
};

int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
GetLenth *get_lenth=new GetLenth(n);
get_lenth->input_edge(m);
get_lenth->Get(s);
delete get_lenth;
return 0;
}

不过堆优化的Dijkstra……

差不多就是吧SPFA的队列换成堆而已(逃

其他的基本没怎么变,还是挺好写的qwq

蒟蒻文化课选手也只能写写这些水题了……