hdu1874 畅通工程续（Dijkstra/Floyd/Bellman-Ford/SPFA）

题意：求最短路。

思路：最短路裸题，四种办法都可以，拿来练习模板了。题目有个坑点WA了一发，两点之间的路可以有多条！

1、Dijkstra算法，适用于无负权图的单源最短路问题。邻接表、邻接矩阵时间复杂度O（n*n），用邻接表+斐波那契堆可以优化到O（m+n*logn）。

代码一：邻接矩阵加暴力方法

#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));
}
}

代码二：邻接表加堆优化

#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）。

#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）。

#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）。

#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 畅通工程续（Dijkstra/Floyd/Bellman-Ford/SPFA）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。