以下都是借来的程序，时间仓促，准备模板用，日后改为自己的。
出处：
https://www.cnblogs.com/yanlifneg/p/5432822.html
https://blog.csdn.net/icecab/article/details/82356929
1：堆优化的dij(边非负）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define M 100000
#define pa pair<int,int>
using namespace std;
int d[M],n,m,cnt,head[M],next[M],u[M],dis[M],num,s,t;
bool f[M];
void add(int from,int to,int di)
{
num++;
u[num]=to;
next[num]=head[from];
head[from]=num;
dis[num]=di;
}
int main()
{
int i;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=m;i++)
{
int uu,vv,d;
scanf("%d%d%d",&uu,&vv,&d);
add(uu,vv,d);
add(vv,uu,d);
}
for (i=1;i<=n;i++)
{
d[i]=2147483647;
}
d[s]=0;
priority_queue<pa,vector<pa>,greater<pa> > q;
q.push(make_pair(0,s));
while(!q.empty())
{
int p=q.top().second;
q.pop();
if(f[p]) continue;
f[p]=1;
for(i=head[p];i;i=next[i])
{
if(d[u[i]]>d[p]+dis[i])
{
d[u[i]]=d[p]+dis[i];
q.push(make_pair(d[u[i]],u[i]));
}
}
}
cout<<d[t]<<endl;
return 0;
}
2：Bellman—Ford（队列优化）
#include<iostream>
#include<stdio.h>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int INF = 2147483647;
const int maxn = 100000+10;
const int maxm = 500000+10;
struct edge
{
int u,v,w;
edge(int u, int v, int w):u(u), v(v), w(w){};
};
int n,m,start, d[maxn], cnt[maxn];
bool inq[maxn];
vector<edge> edges;
vector<int> G[maxn];
bool bellman_ford(int s)
{
int i,u;
queue<int> Q;
inq[s] = true;
Q.push(s);
while(!Q.empty())
{
u = Q.front();
Q.pop();
inq[u] = false;
for(i=0;i<=G[u].size();i++)
{
edge &e = edges[G[u][i]];
if(d[u] < INF && d[e.v] > d[u] + e.w)
{
d[e.v] = d[u] + e.w;
if(!inq[e.v])
{
Q.push(e.v);
inq[e.v] = true;
if (++cnt[e.v] > n) return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d%d",&n,&m,&start);
int i,u,v,w;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(edges.size());
edges.push_back(edge(u,v,w));
}
for (i=1;i<=n;i++)
{
d[i] = INF;
}
d[start] = 0;
bellman_ford(start);
for (i=1;i<=n;i++)
{
printf("%d ",d[i]);
}
printf("n");
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
