情之所至,甘之如饴

Dijkstra

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=100010,maxm=500050,inf=2147483647;
int n,m,s,edgecnt;
struct node {
int v,c;
node *next;
}*h[maxn],pool[maxm];
void addEdge(int u,int v,int c) {
node *p=&pool[++edgecnt];
p->v=v;p->c=c;p->next=h[u];h[u]=p;
}
struct dij {
int id,dis;
bool operator<(const dij t) const {
return dis>t.dis;
}
};
priority_queue<dij> q;
int dis[maxn];
bool vis[maxn];
void dijkstra(int s) {
for(int i=1;i<=n;i++) dis[i]=inf;
memset(vis,0,sizeof(vis));
dij t;
t.id=s;t.dis=0;dis[s]=0;
q.push(t);
while(!q.empty()) {
t=q.top();q.pop();
if(vis[t.id]) continue;
vis[t.id]=true;
int u=t.id;
for(node *p=h[u];p;p=p->next) {
int v=p->v;
if(!vis[v] && dis[v]>dis[u]+p->c) {
dis[v]=dis[u]+p->c;
t.id=v;t.dis=dis[v];
q.push(t);
}
}
}
}
int main() {
int u,v,c;
cin >> n >> m >> s;
for(int i = 1; i<=m; i++)
{
cin >> u >> v >> c;
addEdge(u,v,c);
}
dijkstra(s);
for(int i = 1; i<=n; i++)
cout << dis[i] << " ";
cout << endl;
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=100010,maxm=5000050,inf=2147483647;
int edgecnt;
struct node {
int v,c;
node *next;
}*h[maxn],pool[maxm];
void addEdge(int u,int v,int c) {
node *p=&pool[++edgecnt];
p->v=v;p->c=c;p->next=h[u];h[u]=p;
}
int n,m,s,tim[maxn],dis[maxn];
struct queue {
int q[maxn],head,tail;
queue() {
head=1;tail=0;
}
void push(int x) {
q[++tail]=x;
}
void pop() {
head++;
}
int front() {
return q[head];
}
bool empty() {
return head>tail;
}
int size() {
return tail-head+1;
}
}Q;
bool vis[maxn];
bool spfa(int s) {
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=inf;
Q.push(s);vis[s]=1;dis[s]=0;
int u,v;
while(!Q.empty()) {
u=Q.front();Q.pop();vis[u]=false;
for(node *p=h[u];p;p=p->next) {
v=p->v;
if(dis[v]>dis[u]+p->c) {
dis[v]=dis[u]+p->c;
if(!vis[v]) {
vis[v]=true;
tim[v]++;
Q.push(v);
if(tim[v]>n) return false;
}
}
}
}
return true;
}
int main() {
int u,v,c;
cin >> n >> m >> s;
for(int i = 1; i<=m; i++)
{
cin >> u >> v >> c;
addEdge(u,v,c);
}
spfa(s);
for(int i = 1; i<=n; i++)
cout << dis[i] << " ";
cout << endl;
return 0;
}

Floyd

Kruscal

Prim

Boruvka

Tarjan-SCC

Tarjan-BCC

 评论



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k