题意：求最短路。
思路：最短路裸题，四种办法都可以，拿来练习模板了。题目有个坑点WA了一发，两点之间的路可以有多条！
1、Dijkstra算法，适用于无负权图的单源最短路问题。邻接表、邻接矩阵时间复杂度O（n*n），用邻接表+斐波那契堆可以优化到O（m+n*logn）。
代码一：邻接矩阵加暴力方法
复制代码
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#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<set> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=201; int n,g[N][N]; int dijkstra(int s,int e){ int dis[N]; bool vis[N]; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[s]=0; vis[s]=1; int cur=s; for(int i=1;i<n;++i){ for(int j=0;j<n;++j){ if(!vis[j]&&dis[j]>dis[cur]+g[cur][j]){ dis[j]=dis[cur]+g[cur][j]; } } int mini=inf,id; for(int j=0;j<n;++j){ if(!vis[j]&&dis[j]<mini){ mini=dis[j]; id=j; } } vis[id]=true; cur=id; } if(inf==dis[e])dis[e]=-1; return dis[e]; } int main(){ int m,a,b,c,s,e; while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ g[i][j]=(i==j?0:inf); } } while(m--){ scanf("%d%d%d",&a,&b,&c); if(c<g[a][b]){ g[a][b]=g[b][a]=c; } } scanf("%d%d",&s,&e); printf("%dn",dijkstra(s,e)); } }
代码二：邻接表加堆优化
复制代码
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 <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 1005; struct edg{ int v, d, nxt; }path[maxn * 2]; int pre[maxn], tot; void add(int u, int v, int w) { path[tot].v = v; path[tot].d = w; path[tot].nxt = pre[u]; pre[u] = tot++; } int dist[maxn], n, m; bool vis[maxn]; struct cmp{ bool operator()(int a, int b) { return dist[a] > dist[b]; } }; int dijk(int s, int t) { priority_queue<int, vector<int>, cmp> que; memset(vis, 0, sizeof(vis)); memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; que.push(s); while (!que.empty()) { int cur = que.top(); que.pop(); if (vis[cur]) { continue; } vis[cur] = true; for (int i = pre[cur]; i != -1; i = path[i].nxt) { if (!vis[path[i].v] && dist[cur] + path[i].d < dist[path[i].v]) { dist[path[i].v] = dist[cur] + path[i].d; que.push(path[i].v); } } } return dist[t]; } int main(){ int u, v, w, s, t; while (~scanf("%d%d", &n, &m)) { tot = 0; memset(pre, -1, sizeof(pre)); while (m--) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } scanf("%d%d", &s, &t); int ans = dijk(s, t); printf("%dn", ans == inf ? -1 : ans); } return 0; }
2、Floyd算法，代码简短，可以求出每对点之间的距离，可以求负权，但时间复杂度O（n*n*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#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<set> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=201; int n,g[N][N]; int floyd(){ for(int k=0;k<n;++k){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ if(g[i][j]>g[i][k]+g[k][j]){ g[i][j]=g[i][k]+g[k][j]; } } } } } int main(){ int m,a,b,c,s,e; while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ g[i][j]=(i==j?0:inf); } } while(m--){ scanf("%d%d%d",&a,&b,&c); if(c<g[a][b]){ g[a][b]=g[b][a]=c; } } scanf("%d%d",&s,&e); floyd(); if(g[s][e]==inf)g[s][e]=-1; printf("%dn",g[s][e]); } }
3、Bellman-Ford算法，适用与有负权的图，循环更新路径长，可以检测负环。时间复杂度O（VE）。
复制代码
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#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<set> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=201; int dis[N]; int n,cnt; struct E{ int u,v,cost; }edge[2005]; bool Bellman_Ford(int s,int e){ memset(dis,0x3f,sizeof(dis)); dis[s]=0; for(int i=0;i<n;++i){ for(int j=0;j<cnt;++j){ if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost){ dis[edge[j].v]=dis[edge[j].u]+edge[j].cost; } } } for(int i=0;i<cnt;++i){ if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost){ return false; } } return true; } int main(){ int m,a,b,c,s,e; while(~scanf("%d%d",&n,&m)){ cnt=0; while(m--){ scanf("%d%d%d",&a,&b,&c); edge[cnt].u=a,edge[cnt].v=b,edge[cnt++].cost=c; edge[cnt].u=b,edge[cnt].v=a,edge[cnt++].cost=c; } scanf("%d%d",&s,&e); Bellman_Ford(s,e); if(dis[e]==inf)dis[e]=-1; printf("%dn",dis[e]); } }
4、SPFA算法，用队列优化，适用于存在负权的图。时间复杂度O（k*E），k是点进入队列的时间，一般2、3次，最坏复杂度O（VE）。
复制代码
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#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<set> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=201; int n,g[N][N]; int spfa(int s,int e){ int dis[N]; int vis[N]; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[s]=0; vis[s]=true; queue<int> q; q.push(s); while(!q.empty()){ int cur=q.front(); q.pop(); vis[cur]=false; for(int i=0;i<n;++i){ if(dis[i]>dis[cur]+g[cur][i]){ dis[i]=dis[cur]+g[cur][i]; if(!vis[i]){ q.push(i); vis[i]=true; } } } } if(dis[e]==inf)dis[e]=-1; return dis[e]; } int main(){ int m,a,b,c,s,e; while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ g[i][j]=(i==j?0:inf); } } while(m--){ scanf("%d%d%d",&a,&b,&c); if(c<g[a][b]){ g[a][b]=g[b][a]=c; } } scanf("%d%d",&s,&e); printf("%dn",spfa(s,e)); } }
最后
以上就是腼腆发带最近收集整理的关于hdu1874 畅通工程续（Dijkstra/Floyd/Bellman-Ford/SPFA）的全部内容，更多相关hdu1874内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复