图论3——单源最短路模板
以下都是借来的程序，时间仓促，准备模板用，日后改为自己的。
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄
出处：
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; }
更多精彩
