3.7bellman-ford
Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路
时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
int n, m; // n表示点数，m表示边数 int dist[N]; // dist[x]存储1到x的最短路距离 struct Edge // 边，a表示出点，b表示入点，w表示边的权重 { int a, b, w; }edges[M]; // 求1到n的最短路距离，如果无法从1走到n，则返回-1。 int bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } if (dist[n] > 0x3f3f3f3f / 2) return -1; return dist[n]; }
3.7.1 853. 有边数限制的最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
#include<bits/stdc++.h> using namespace std; const int N=510,M=10010,INF=0x3f3f3f3f; int n,m,k; struct Edge{ int a,b,w; }; Edge edges[M]; int dis[N],backup[N]; int bellman_ford() { fill(dis,dis+N,INF); dis[1]=0; for(int i=0;i<k;i++) { memcpy(backup,dis,sizeof dis); for(int j=0;j<m;j++) { Edge e=edges[j]; dis[e.b]=min(dis[e.b],backup[e.a]+e.w); } } if(dis[n]>INF/2) return -1; return dis[n]; } int main() { cin>>n>>m>>k; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; edges[i].a=a,edges[i].b=b,edges[i].w=w; } int ans=bellman_ford(); if(ans==-1) cout<<"impossible"; else cout<<dis[n]; return 0; }
3.8spfa
spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数 bool st[N]; // 存储每个点是否在队列中 // 如果存在负环，则返回true，否则返回false。 bool spfa() { // 不需要初始化dist数组 // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。 queue<int> q; for (int i = 1; i <= n; i ++ ) { q.push(i); st[i] = true; } while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } } return false; }
3.8.1 851. spfa求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
#include<bits/stdc++.h> using namespace std; const int N=100010,INF=0x3f3f3f3f; int h[N],e[N],w[N],ne[N],idx; int n,m; int dis[N]; bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int spfa(int s) { fill(dis,dis+N,INF); dis[s]=0; queue<int> q; q.push(s); while(!q.empty()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } if(dis[n]==INF) return -1; else return dis[n]; } int main() { cin>>n>>m; fill(h,h+N,-1); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t=spfa(1); if(t==-1) cout<<"impossible"; else cout<<t; return 0; }
3.8.2 852. spfa判断负环
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes
#include<bits/stdc++.h> using namespace std; const int N=100010,INF=0x3f3f3f3f; int h[N],e[N],w[N],ne[N],idx; int n,m; int dis[N]; bool st[N]; int cnt[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { fill(dis,dis+N,INF); dis[1]=0; queue<int> q; for(int i=1;i<=n;i++) { q.push(i); st[i]=true; } while(!q.empty()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { cin>>n>>m; fill(h,h+N,-1); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } if(spfa()) cout<<"Yes"; else cout<<"No"; return 0; }
3.9Floyd
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 算法结束后，d[a][b]表示a到b的最短距离 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]); }
3.9.1 854. Floyd求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
#include<bits/stdc++.h> using namespace std; const int N=210,M=20010,INF=1e9; int n,m,k; int d[N][N]; void Floy() { 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]); } int main() { cin>>n>>m>>k; fill(d[0],d[0]+N*N,INF); for(int i=1;i<=n;i++) { d[i][i]=0; } for(int i=1;i<=m;i++) { int x,y,w; cin>>x>>y>>w; d[x][y]=min(d[x][y],w); } Floy(); while(k--) { int x,y; cin>>x>>y; if(d[x][y]>INF/2) cout<<"impossible"<<endl; else cout<<d[x][y]<<endl; } return 0; }
