单源最短路径

【模板】单源最短路径(弱化版)
P4779 【模板】单源最短路径(标准版)
Floyd

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
#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
#define maxn 10005
int e[maxn][maxn],n,m,S;
inline int read() {
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')k=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int main() {
cin>>n>>m>>S;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(i==j)e[i][j]=0;
else e[i][j]=inf;
}
}
for(int i=1; i<=m; i++) {
int x,y,z;
x=read();
y=read();
z=read();
e[x][y]=min(e[x][y],z);
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
for(int k=1; k<=n; k++) {
if(e[j][i] < inf && e[i][k] < inf && e[j][k] > e[j][i] + e[i][k])
e[j][k] = e[j][i] + e[i][k];
}
}
}
for(int i=1; i<=n; i++) {
printf("%d ",e[S][i]);
}
return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 10000+5
#define INF 10000000
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int W[maxn][maxn],dis[maxn];
bool book[maxn];
int n,m,s;
int main() {
n=read();
m=read();
s=read();
memset(W,0x3f,sizeof(W));
memset(dis,0x3f,sizeof(dis));
for(register int i=1; i<=m; i++) {
int u,v,w;
u=read();
v=read();
w=read();
W[u][v]=w;
}
dis[s]=0;
for(register int i=1; i<=n; i++) {
int x,Min=INF;
for(register int j=1; j<=n; j++) {
if(book[j]==0&&dis[j]<=Min) {
Min=dis[j];
x=j;
}
}
book[x]=1;
for(register int j=1; j<=n; j++) {
dis[j]=min(dis[j],dis[x]+W[x][j]);
}
}
for(register int i=1; i<=n; i++) {
cout<<dis[i]<<' ';
}
return 0;
}

bellman-ford

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
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define maxn 500005
long long dis[10100];
int f[maxn],g[maxn],w[maxn],n,m,s;
bool check;
inline int read() {
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')k=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int main() {
cin>>n>>m>>s;
for(int i=1; i<=m; i++) {
f[i]=read();
g[i]=read();
w[i]=read();
}
for(int i=1; i<=n; i++) {
dis[i]=inf;
}
dis[s]=0;
int k=n-1;
while(k--) {
check=0;
for(int i=1; i<=m; i++) {
if(dis[g[i]]>dis[f[i]]+w[i]) {
dis[g[i]]=dis[f[i]]+w[i];
check=1;
}
}
if(check==0) {
break;
}//假如不在变化,直接退出
}
for(int i=1; i<=n; i++) {
printf("%d ",dis[i]);
}
return 0;
}

SPFA

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000+5
#define INF 2147483647
inline int read() {
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')k=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int n,m,s;
int u[maxn],v[maxn],w[maxn],dis[maxn];
bool book[maxn];
int first[maxn],next[maxn];
void firs_t() {
n=read();
m=read();
s=read();
memset(first,-1,sizeof(first));
for(register int i=1;i<=maxn;i++){
dis[i]=INF;
}
return;
}
int main() {
firs_t();
for(register int i=1; i<=m; i++) {
u[i]=read();
v[i]=read();
w[i]=read();
next[i]=first[u[i]];
first[u[i]]=i;
}
queue<int> q;
q.push(s);
book[s]=1;
dis[s]=0;
while(!q.empty()) {
int k=first[q.front()];
while(k!=-1) {
if(dis[v[k]]>dis[u[k]]+w[k]) {
dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0) {
q.push(v[k]);
book[v[k]]=1;
}
}
k=next[k];
}
book[q.front()]=0;
q.pop();
}
for(register int i=1; i<=n; i++) {
printf("%d ",dis[i]);
}
return 0;
}
//SPFA!!!

优先队列SPFA

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000+5
#define INF 2147483647
inline int read() {
int x=0,k=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')k=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
int n,m,s;
int u[maxn],v[maxn],w[maxn],dis[maxn];
bool book[maxn];
int first[maxn],next[maxn];
void firs_t() {
n=read();
m=read();
s=read();
memset(first,-1,sizeof(first));
for(register int i=1; i<=maxn; i++) {
dis[i]=INF;
}
return;
}
struct cmp {
bool operator()(int a,int b) {
return dis[a]>dis[b];
}
};
int main() {
firs_t();
for(register int i=1; i<=m; i++) {
u[i]=read();
v[i]=read();
w[i]=read();
next[i]=first[u[i]];
first[u[i]]=i;
}
priority_queue<int,vector<int>,cmp> q;
q.push(s);
book[s]=1;
dis[s]=0;
while(!q.empty()) {
int k=first[q.top()];
while(k!=-1) {
if(dis[v[k]]>dis[u[k]]+w[k]) {
dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0) {
q.push(v[k]);
book[v[k]]=1;
}
}
k=next[k];
}
book[q.top()]=0;
q.pop();
}
for(register int i=1; i<=n; i++) {
printf("%d ",dis[i]);
}
return 0;
}
//SPFA!!!