Dijkstra
数组存储
大致步骤:
1. 外层为n次循环，内层两个循环
2. 第一个循环用来找到没有用过的并且 距离点1最小的点 ，用t存储
3. 利用t作为中间点去遍历每个结点，dist[j]=min(dist[j],dist[t]+g[t][j]);
// 注意有重边的情况
int d(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;
}
if(t==-1||dist[t]==0x3f3f3f3f)return -1;
st[t]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
return dist[n];
}
链式存储
大致步骤：
1. 利用优先队列（最小根），存储PII(距离，结点)
2. 已经出队过的点，st[ver]=true;
3. 遍历每个儿子，入队
int d()
{
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII> ,greater<PII>> heap;
heap.push({0,1});
while(heap.size())
{
PII t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver])continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>distance+w[i])
{
dist[j]=distance +w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
bf -> 解决有边数限制的最短路
大致步骤为：
1. 将每条边用结构体存下来，(a,b,c);
2. 外层k次循环,需要的边
3. 内层利用一个循环数组（back==dist)
4. 遍历每条边 dist[b]=min(dist[b],back[a]+w);
int bf()
{
dist[1]=0;
for(int i=1;i<=k;i++)
{
memcpy(back,dist,sizeof dist);
for(int j=1;j<=m;j++)
{
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
dist[b]=min(dist[b],back[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2)return -1;
return dist[n];
}
spfa 算法最短路
大致步骤为：
1. 链式存储，队列存储结点
2. 遍历每个儿子，入队就st[i]=true,出队st[i]=false;
void spfa(){
memset(dist,0x3f,sizeof dist);
queue<int> heap;
heap.push(1);
dist[1]=0;
st[1]=true;
while(heap.size()){
int top =heap.front();
heap.pop();
st[top]=false;
for(int i=h[top];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[top]+w[i]){
dist[j]=dist[top]+w[i];
if(!st[j]){
st[j]=true;
heap.push(j);
}
}
}
}
if(dist[n]==0x3f3f3f3f)puts("impossible");
else cout<<dist[n]<<endl;
}
Floyd -> 任意两个结点的距离
1 .三层循环，中间点，两端点
void floyd() {
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
最小生成树
prim算法->数组存储
大致步骤：
1. 外层循环为n次
2. 第一个循环用来找到没有用过的并且 距离当前生成树最近的点 ，用t存储
3. dist[t]==INF，说明无最小生成树,ret+=dist[t],并标记为走过
4. 遍历每个点，更新值为当前生成树最近的点
int prim()
{
int ret=0;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
if(dist[t]==INF)return INF;
st[t]=true;
ret+=dist[t];
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
}
return ret;
}
Kruskal ->并查集
- 将边用结构体存下来（a,b,c）
- 按照边的权值从小到大排序
- 遍历每条边
- 如果两个端点不属于一个集合（初始每个点都指向自己），就让他们成为一个集合，边的数量增加，res+=该边的权值。
- cnt!=n-1 表示无法生成最小生成树
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010,M=100010;
int p[M];
int n,m;
struct Edge
{
int a,b,w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
else return x;
}
int Kruskal()
{
int res=0,cnt=0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
for(int i=0;i<m;i++)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
if(find(a)!=find(b))
/*
具体可以参考连通块中点的数量,如果a和b已经在一个集合当中了,说明这两个点已经被一种方式连接起来了,
如果加入a-b这条边,会导致集合中有环的生成,而树中不允许有环生成,所以一个连通块中的点的数量假设
为x,那么里面x个节点应该是被串联起来的,有x-1条边,所以只有当a,b所属的集合不同时,才能将a-b这条
边加入到总集合当中去
*/
{
p[find(a)]=p[find(b)];//将a,b所在的两个集合连接起来
cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
res+=w;//加入到集合中的边的权重之和
}
}
if(cnt==n-1) return res;//可以生成最小生成树
else return 0x3f3f3f3f;//树中有n个节点便有n-1条边,如果cnt不等于n-1的话,说明无法生成有n个节点的树
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) p[i]=i;//初始化并查集
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
sort(edges,edges+m);//将边的权重按照大小一一排序
int t=Kruskal();
if(t==0x3f3f3f3f) printf("impossible\n");
else printf("%d\n",t);
return 0;
}
