1.Floyd
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
const int inf=0x3f3f3f3f;
int g[N][N],n,m;
void floyd()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
///必要时剪枝
///if(g[i][k]<inf)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
}
}
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
g[i][j]=inf;
}
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(c<g[a][b])
g[a][b]=g[b][a]=c;
}
floyd();
cout<<g[1][n]<<'\n';
}
return 0;
}(/▽＼) 新加~floyd对无向图的优化 https://blog.csdn.net/lanshuizhiyun/article/details/77864648
2.Dijkstra
<1>朴素版
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
const int inf=0x3f3f3f3f;
int g[N][N],dis[N],vis[N];
int n,m;
void dijk()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
dis[i]=g[1][i];
vis[1]=1;
dis[1]=0;
for(int i=1;i<=n;i++)
{
int pos,minn=inf;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&minn>dis[j])
{
pos=j;
minn=dis[j];
}
}
vis[pos]=1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]>dis[pos]+g[pos][j])
dis[j]=dis[pos]+g[pos][j];
}
}
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=inf;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(c<g[a][b])
g[a][b]=g[b][a]=c;
}
dijk();
cout<<dis[n]<<'\n';
}
return 0;
}
<2>dijkstra+堆优化（邻接矩阵存图）
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10;
int n,m;
struct qnode
{
int v;
int c;
qnode(int _v=0,int _c=0):v(_v),c(_c){}
bool operator <(const qnode &r)const
{
return c>r.c;
}
};
struct Edge
{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[N];
bool vis[N];
int dis[N];
void dijk(int n,int start)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
dis[i]=inf;
priority_queue<qnode>q;
while(!q.empty())
q.pop();
dis[start]=0;
q.push(qnode(start,0));
qnode tmp;
while(!q.empty())
{
tmp=q.top();
q.pop();
int u=tmp.v;
if(vis[u])
continue;
vis[u]=true;
for(int i=0;i<E[u].size();i++)
{
int v=E[tmp.v][i].v;
int cost=E[u][i].cost;
if(!vis[v]&&dis[v]>dis[u]+cost)
{
dis[v]=dis[u]+cost;
q.push(qnode(v,dis[v]));
}
}
}
}
void addadge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
void init()
{
for(int i=0;i<N;i++)
E[i].clear();
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
init();
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
addadge(u,v,w);///注意无向图加两条边
addadge(v,u,w);
}
dijk(n,1);
cout<<dis[n]<<'\n';
}
return 0;
}<3>dijkstra+堆优化（链式前向星存图）
大佬的链式前向星详解
#include <bits/stdc++.h> ///dijk+堆优化（链式前向星）
using namespace std;
const int N = 1e4 + 7;
const int inf = 0x3f3f3f3f;
int head[N];
bool vis[N];
int dis[N];
int n, m, tot;
struct Node
{
int u, v, l, next; ///起点 终点 长度 与该边同起点的上一条边的储存位置
}edge[N];
struct A
{
int pos, cost;
bool operator < (const A &a)const
{
return cost > a.cost;
}
};
void addedge(int x, int y, int z)
{
edge[tot].u = x;
edge[tot].v = y;
edge[tot].l = z;
edge[tot].next = head[x];
head[x] = tot++;
}
int dijk(int src, int des)
{
memset(dis, inf, sizeof(dis));
memset(vis, 0, sizeof(vis));
priority_queue<A>q;
dis[src] = 0;
A now;
now.cost = 0;
now.pos = src;
q.push(now);
while(!q.empty())
{
now = q.top();
q.pop();
if(vis[now.pos])
continue;
vis[now.pos] = 1;
for(int i = head[now.pos]; ~i; i = edge[i].next) //遍历以该点为顶点的所有边
{
int to = edge[i].v; //to = 这条边的终点
if(!vis[to] && dis[to] > edge[i].l + dis[edge[i].u]) //to没有更新过且目前源点到to的距离 > 该边的长度 + 源点到该边起点的距离
{
dis[to] = dis[edge[i].u] + edge[i].l; //更新
now.cost = dis[to];
now.pos = to;
q.push(now);
}
}
}
return dis[des];
}
int main()
{
int u, v, w;
while(scanf("%d%d", &n, &m) != EOF && n + m)
{
tot = 0;
memset(head, -1, sizeof(head));
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
int ans = dijk(1, n);
cout<<ans<<'\n';
}
return 0;
}
<4>dijkstra+堆优化（pair存储）
3.Bellman-ford
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N];
int n,m;
struct Edge
{
int u,v,w;
}edge[N];
bool Bellman_Ford()
{
for(int i=1;i<=n;i++)
dis[i]=inf;
dis[1]=0;
for(int k=1;k<=n-1;k++)
{
bool flag=0;
for(int i=1;i<=2*m;i++)
{
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
{
dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
flag=1;
}
}
if(!flag)
return true;
}
for(int j=1;j<=2*m;j++)
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
return false;///判负环
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
int cnt=1;
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[cnt].u=edge[cnt+1].v=a;
edge[cnt].v=edge[cnt+1].u=b;
edge[cnt].w=edge[cnt+1].w=c;
cnt+=2;
}
if(Bellman_Ford())
cout<<dis[n]<<'\n';
else
cout<<-1<<'\n';
}
return 0;
}4.spfa
<1>朴素版（链式前向星）
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],vis[N],head[N],num[N];
int n,m,tot;
struct Edge
{
int u,v,w,next;
}edge[N];
void add(int a,int b,int c)
{
edge[tot].u=a;
edge[tot].v=b;
edge[tot].w=c;
edge[tot].next=head[a];
head[a]=tot++;
}
bool spfa(int s)
{
queue<int>q;
for(int i=1;i<=n;i++)
dis[i]=inf;
memset(vis,false,sizeof(vis));
memset(num,0,sizeof(num));
q.push(s);
dis[s]=0;
vis[s]=1;
while(!q.empty())
{
int pos=q.front();
q.pop();
vis[pos]=false;
num[pos]++;
for(int i=head[pos];i!=-1;i=edge[i].next)
{
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
{
dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
if(!vis[edge[i].v])
{
vis[edge[i].v]=true;
q.push(edge[i].v);
if(num[edge[i].v]>=n)
return false;
}
}
}
}
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
int a,b,c;
tot=0;
memset(head,-1,sizeof(head));
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
if(!spfa(1))
cout<<-1<<'\n';
else
cout<<dis[n]<<'\n';
}
return 0;
}
<2>SLF优化（链式前向星）
#include <bits/stdc++.h>///spfa SLF优化
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],head[N];
bool vis[N];
int n,m,tot;
struct Edge
{
int u,v,w,next;
}edge[N];
void add(int a,int b,int c)
{
edge[tot].u=a;
edge[tot].v=b;
edge[tot].w=c;
edge[tot].next=head[a];
head[a]=tot++;
}
void spfa(int s)
{
deque<int>q;
memset(dis,inf,sizeof(dis));
memset(vis,false,sizeof(vis));
vis[s]=true;
dis[s]=0;
q.push_back(s);
while(!q.empty())
{
int from=q.front();
q.pop_front();
vis[from]=false;
for(int i=head[from];i!=-1;i=edge[i].next)
{
int to=edge[i].v;
if(dis[to]>dis[from]+edge[i].w)
{
dis[to]=dis[from]+edge[i].w;
if(!vis[to])
{
if(!q.empty()&&dis[to]>=dis[q.front()])///注意
q.push_back(to);
else
q.push_front(to);
vis[to]=true;
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
int a,b,c;
tot=0;
memset(head,-1,sizeof(head));
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa(1);
cout<<dis[n]<<'\n';
}
return 0;
}<3>SLF+LLL优化（链式前向星）
#include <bits/stdc++.h>///spfa SLF+LLL优化
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],head[N];
bool vis[N];
int n,m,tot;
struct Edge
{
int u,v,w,next;
}edge[N];
void add(int a,int b,int c)
{
edge[tot].u=a;
edge[tot].v=b;
edge[tot].w=c;
edge[tot].next=head[a];
head[a]=tot++;
}
void spfa(int s)
{
int num=0;
long long sum=0;
deque<int>q;
memset(dis,inf,sizeof(dis));
memset(vis,false,sizeof(vis));
vis[s]=true;
dis[s]=0;
q.push_back(s);
num++;
while(!q.empty())
{
int from=q.front();
q.pop_front();
num--;
sum-=dis[from];
while(num&&dis[from]>sum/num)
{
q.push_back(from);
from=q.front();
q.pop_front();
}
vis[from]=false;
for(int i=head[from];i!=-1;i=edge[i].next)
{
int to=edge[i].v;
if(dis[to]>dis[from]+edge[i].w)
{
dis[to]=dis[from]+edge[i].w;
if(!vis[to])
{
if(!q.empty()&&dis[to]<dis[q.front()])
q.push_front(to);
else
q.push_back(to);
vis[to]=true;
num++;
sum+=dis[to];
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
int a,b,c;
tot=0;
memset(head,-1,sizeof(head));
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa(1);
cout<<dis[n]<<'\n';
}
return 0;
}
京公网安备 11010502036488号