bfs

在搜索题中，一般来讲，bfs和dfs都有一个最优选择。

基础bfs

走迷宫

• 注：这个模板具有还原路径的功能。
• 其实，还可以反向搜（从终点走到起点），就不用
  reverse数组了。
• 其实，bfs是不用把路径标为INF的，也用不到vis数组的。只需要将d初始化为-1就可以，想想是不是？！

typedef pair<int, int> P;
int g[maxn][maxn], N, d[maxn][maxn], dx[] = { 0, 0, 1, -1 }, dy[] = {1, -1, 0, 0};
P pre[maxn][maxn];
queue<P> que;
vector<P> path;
void bfs() {memset(d, -1, sizeof d);que.push({ 0, 0 });d[0][0] = 0, pre[0][0] = { -1, -1 };while (que.size()) {auto p = que.front(); que.pop();int x = p.first, y = p.second;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;if (g[nx][ny] || d[nx][ny] != -1) continue;d[nx][ny] = d[x][y] + 1;pre[nx][ny] = { x, y };que.push({ nx, ny });}}for (auto p = P(N - 1, N - 1); p != P(-1, -1); p = pre[p.first][p.second]) {path.push_back(p);}reverse(path.begin(), path.end());for (auto p : path) {printf("%d %d\\n", p.first, p.second);}
}

920. 最优乘车

• 题意：每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到 $H$ 城旅游，他很想去 $S$ 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 $S$ 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 $S$ 公园。现在用整数 $1,2,\dots N$ 给 $H$ 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 $1$，$S$ 公园巴士站的编号为 $N$。写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 $S$ 公园的过程中换乘的次数最少。

• 输入格式：第一行有两个数字 $M$ 和 $N$，表示开通了 $M$ 条单程巴士线路，总共有 $N$ 个车站。从第二行到第 $M+1$ 行依次给出了第 $1$ 条到第 $M$ 条巴士线路的信息，其中第 $i+1$ 行给出的是第 $i$ 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

• 目前发现（大雪菜也说过），当边权都为1的时候，通常就是用 bfs 来写，而不是用 spfa，dijkstra 这种方法。

• 其实，这和迷宫的那个模型差不太多，而且还简单一些。

• 这道题保留的意义其实是掌握以下 stringstream 和 getline(cin, line) 的用法。

#include<sstream>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 510, INF = 1e9;
int g[maxn][maxn], N, M, d[maxn];
void bfs() {fill(d, d + maxn, INF);queue<int> que;que.push(1);d[1] = 0;while (que.size()) {int u = que.front(); que.pop();for (int j = 1; j <= N; j++) {if (g[u][j] && d[j] > d[u] + 1) {d[j] = d[u] + 1;que.push(j);}}}
}
int main() {cin >> M >> N;string line;getline(cin, line);for (int i = 0; i < M; i++) {getline(cin, line);stringstream ss(line);vector<int> v;int u;while (ss >> u) v.push_back(u);for (int i = 0; i < v.size(); i++) {for (int j = 0; j < i; j++) g[v[j]][v[i]] = 1;}}bfs();int ans = d[N];if (ans == INF) printf("NO\\n");else printf("%d\\n", ans - 1);return 0;
}

Flood Fill

1097. 池塘计数

• 题意：$n\ast m$ 的园子，雨后起了积水。八连通的积水被认为是连在一起的。问总共有多少水洼。

• dfs可能会爆栈，因此这里展示bfs的做法。

• 连通块分为四连通和八连通。

• 注意，这个题是可以把 queue 当作全局变量的。因为在 bfs 中，只有 queue 为空是才能跳出循环。

int N, M;
char g[maxn][maxn];
bool vis[maxn][maxn];
typedef pair<int, int> P;
queue<P> que;
void bfs(int x, int y) {que.push({ x, y });vis[x][y] = true;while (que.size()) {auto p = que.front(); que.pop();int x = p.first, y = p.second;for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {int nx = x + dx, ny = y + dy;if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (vis[nx][ny] || g[nx][ny] == '.') continue;vis[nx][ny] = true;que.push({ nx, ny });}}}
}
void solve() {int ans = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (g[i][j] == 'W' && !vis[i][j]) {bfs(i, j);ans++;}}}printf("%d\\n", ans);
}

173. 矩阵距离

• 给定一个N行M列的01矩阵A，$A[i][j]$ 与 $A[k][l]$ 之间的曼哈顿距离定义为：

$$dist(A[i][j],A[k][l])=|i-k|+|j-l|$$

• 输出一个N行M列的整数矩阵B，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1⁡dist(A[i][j],A[x][y])B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}⁡{dist(A[i][j],A[x][y])} B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1​⁡dist(A[i][j],A[x][y])

• 多源 BFS 问题.
• 虚拟源点，无需解释，直接上代码。

queue<P> que;
void bfs() {memset(d, -1, sizeof d);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (g[i][j] == '1') {d[i][j] = 0;que.push(P(i, j));}}}while (que.size()) {auto p = que.front(); que.pop();int x = p.first, y = p.second;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M || d[nx][ny] != -1) continue;d[nx][ny] = d[x][y] + 1;que.push(P(nx, ny));}}
}

双端队列广搜

• 双端队列广搜就是边权可以是0或1
• 在一个边权只有0、1的无向图中搜索最短路径可以使用双端队列进行BFS。其原理是当前可以扩展到的点的权重为0时，将其加入队首；权重为1时，将其加入队尾。

175. 电路维修

• 这道题并不是所有节点都可以访问到的。只能访问到下标值和为偶数的节点。当中点下标之和为奇数的时候就访问不到。
• 注意这个偏移量数组的灵活运用 (dx, ix, ok).
• 这迷宫的终点是(N, M)，一定注意！而且下标是从0开始的。而且注意要取出队头pop_front()。
• 这道题判断重复访问的位置只能放到从 deque 取出的地方，不可以往后放。因为这个节点访问顺序不好保证。
• 双端队列广搜有一个和bfs不一样的地方，即第一次从双端队列弹出的是最短距离，但是第一次更新的时候并不是！因此，判断节点是否被访问过，以及更新距离的方式，都要改变。而bfs第一次更新的时候就已经是最短距离了。

bool vis[maxn][maxn];
char g[maxn][maxn];
int dx[] = { 1, 1, -1, -1 }, dy[] = { 1, -1, 1, -1 };
int ix[] = { 0, 0, -1, -1 }, iy[] = { 0, -1, 0, -1 };
const char* ok = "\\\\//\\\\";
int bfs() {for (int i = 0; i <= N; i++) {for (int j = 0; j <= M; j++) {d[i][j] = INF;}}memset(vis, false, sizeof vis);deque<P> dq;d[0][0] = 0;dq.push_back(P(0, 0));while (dq.size()) {auto p = dq.front(); dq.pop_front();int x = p.first, y = p.second;if (x == N && y == M) return d[x][y];if (vis[x][y]) continue;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx > N || ny < 0 || ny > M) continue;int w = (g[x + ix[i]][y + iy[i]] != ok[i]);if (d[nx][ny] >= d[x][y] + w) {d[nx][ny] = d[x][y] + w;if (w) dq.push_back(P(nx, ny));else dq.push_front(P(nx, ny));}}}
}

双向广搜

• 可以对bfs剪枝，即从两个方向同时搜索，而不是向一个方向搜索。

• 双向广搜和A*适用条件比较类似，都是在搜索空间非常庞大的时候。

  190. 字串变换

• 给定一些字符串变换规则（从一个字符串变成另一个字符串），问最少需要多少步才能把 $A$ 变为 $B$.

• 每次选择队列元素较少的一个方向扩展。

#include<iostream>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
string a[10], b[10], A, B;
int N;
int extend(queue<string>& que, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[]) {string st = que.front(); que.pop();string ed;for (int i = 0; i < st.size(); i++) {for (int j = 0; j < N; j++) {if (st.substr(i, a[j].size()) == a[j]) {ed = st.substr(0, i) + b[j] + st.substr(i + a[j].size());if (db.count(ed)) return da[st] + 1 + db[ed];if (da.count(ed)) continue;da[ed] = da[st] + 1;que.push(ed);}}}return 11;
}
int bfs() {queue<string> qa, qb;unordered_map<string, int> da, db;qa.push(A), qb.push(B), da[A] = 0, db[B] = 0;//因为只要又一个队列为空，那么必然从起点无法转移到终点了。while (qa.size() && qb.size()) {int t;if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);else t = extend(qb, db, da, b, a);if (t <= 10) return t;}return 11;
}
int main() {cin >> A >> B;while (cin >> a[N] >> b[N]) N++;int ans = bfs();if (ans > 10) cout << "NO ANSWER!\\n";else cout << ans << endl;return 0;
}

A*

• 用一个小根堆，维护两个值，一个是从起点到当前点的最短距离，另一个是从当前点到终点的估计距离。
• A* 算法就是挑一个估计距离最小的点去扩展。估计距离必须不能超过真实距离，而且要非负，这样才能保证A*算法一定正确。百度百科：距离估计与实际值越接近，最终搜索速度越快。
• A* 算法只有在有解的情况下才是高效的。否则还不如朴素的bfs效率高。因为A*是用优先队列来实现的。
• A* 只能保证终点出队的时候，距离最小，但不能保证每一个点出队的时候都是最小的。
• A* 算法边权只要没有负权回路就是用。Dijkstra在形式上可以看成估计距离为0的A*算法。

178. 第K短路

• 整个搜索空间非常庞大。
• 由于百科中说估计值与真实值越接近，最终搜索速度越快。所以这里选择到终点的最短路作为估计值（可以建反图来求得）。
• 第几次出队就是第几短,于是终点出了k次就是第k短路了。
• 这道题容易漏掉两种无解的情况：起点与终点重合，起点与终点不连通。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> P3;
const int maxn = 1010, maxm = 100010, INF = 0x3f3f3f3f;
int h[maxn], hr[maxn], ne[maxm], e[maxm], w[maxm], idx;
int N, M, S, T, K, d[maxn];
bool vis[maxn];
void add(int h[], int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void dijkstra() {priority_queue<P, vector<P>, greater<P>> que;fill(d, d + maxn, INF);d[T] = 0; que.push(P(0, T));while (que.size()) {auto p = que.top(); que.pop();int u = p.second;if (vis[u]) continue;vis[u] = true;for (int i = hr[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] > d[u] + w[i]) {d[v] = d[u] + w[i];que.push(P(d[v], v));}}}
}
int astar() {//若起点与终点不连通，也是无解吖。。。if (d[S] == INF) return -1;priority_queue<P3, vector<P3>, greater<P3>> que;que.push(P3(d[S], P(0, S)));int cnt = 0;while (que.size()) {auto p = que.top(); que.pop();int u = p.second.second, dis = p.second.first;if (u == T) cnt++;if (cnt == K) return dis;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];//如何判断所有路径？就是不经判断，把所有经过的路径全部加进来。que.push(P3(dis + w[i] + d[v], P(dis + w[i], v)));}}return -1;
}
int main() {memset(h, -1, sizeof h);memset(hr, -1, sizeof hr);scanf("%d%d", &N, &M);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(h, a, b, c);add(hr, b, a, c);}scanf("%d%d%d", &S, &T, &K);//因为题中说路径至少包含一条边，因此，对于起点和终点重合的情况，若想让路径至少包含一条边，要这样处理：if (S == T) K++;dijkstra();printf("%d\\n", astar());
}

图论

遍历问题

（1）树和图的深度优先遍历

• 这里讲一下树的存储。综上来看，还是要掌握用单链表实现临界点存储，因为比较快。
• h[i]储存的是头结点，其实就是i节点指向的一条边的编号idx。而这个链表存储的是第i个节点指向的所有的边。注意，idx是边的编号。
• 注意，h 储存的是节点信息，e 和 ne 储存的是边的信息。e存储的是边指向的节点（相当于to），而ne存储的是这条边指向该头结点的下一条边。如果再有w[idx]的话，指的是编号idx的边的权重。
• 由于h[i]存储的指向的边顺序无所谓，因此插入边的时候用前插法，更好实现。
• 链表初始化，就是全部初始化为-1，这样当ne[i]为-1时，表示结束。
• 邻接表存储：

int h[N], e[N], ne[N], idx;// 添加一条边a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 初始化
idx = 0;
memset(h, -1, sizeof(h));
//树与图的遍历（深度优先遍历）
//时间复杂度 O(n+m) n 表示点数，m 表示边数int dfs(int u)
{st[u] = true; // st[u] 表示点u已经被遍历过for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!st[j]) dfs(j);}
}

树的重心

• 给定一颗树。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
• 这道题一直WA的原因是双向边，但是边的数组最开始开小了。双向边的话，数组一定要开到两倍！

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100005, maxm = maxn * 2;
int h[maxn], e[maxm], ne[maxm], idx, N, ans;
bool vis[maxn];  //该节点是否访问过。
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u) {vis[u] = true;//res储存各个连通块中点数的最大值，sum储存从节点u出发的子树的大小。int res = 0, sum = 1;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (!vis[v]) {int s = dfs(v);res = max(res, s);sum += s;}}//N - sum是上面的那个连通块的大小res = max(res, N - sum);ans = min(res, ans);return sum;
}
int main() {for (int i = 0; i < maxn; i++) h[i] = -1;int a, b;scanf("%d", &N);ans = N;for (int i = 0; i < N - 1; i++) {scanf("%d%d", &a, &b);add(a, b), add(b, a);}dfs(1);printf("%d\\n", ans);return 0;
}

树的同构

树是一种很常见的数据结构。我们把 $N$ 个点，$N-1$ 条边的连通无向图称为树。若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。对于两个树 T1T_1T1​ 和 T2T_2T2​，如果能够把树 T1T_1T1​ 的所有点重新标号，使得树 T1T_1T1​ 和树 T2T_2T2​ 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你 $M$ 个无根树，请你把它们按同构关系分成若干个等价类.

注意这个题的输入，树的编号是 $1\sim N$，结点父结点编号为 $0$ 说明该点没有父结点.

(wsy) 最难卡掉的树哈希方法：$rd$ 数组是一个随机数生成的数组：h[i] = rnd() % M，其中 $M$ 是一个大质数.

叶节点的哈希值定义为1.
Hash(TR)=∏i∈son(R)(rd(size(TR)+Hash(Ti))modMHash(T_R) = \\prod\\limits_{i \\in son(R)}(rd(size(T_R) + Hash(T_i)) \\mod M Hash(TR​)=i∈son(R)∏​(rd(size(TR​)+Hash(Ti​))modM
对于无根树，可以先求树的重心作为根，如果重心有两个就建立虚拟节点连接两个重心，把虚拟节点当作根节点.

判断无根树同构，也可以跑两遍树形DP，求出每个点为根时的Hash值，排序后比较即可。不过应该需要用到 fx=1+∑y∈sonxfy×prime(sizey)f_x = 1 + \\sum_{y\\in son_x}{f_y \\times prime(size_y)}fx​=1+∑y∈sonx​​fy​×prime(sizey​)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 60, M = 110;int h[N], e[M], ne[M], idx, sz[N], weight[N];
ll Hash[N], Hash_tree[N];
int centroid[2];
inline void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
mt19937 rnd(0);
int n, m;//求树的重心
int getCentroid(int u, int fa)
{sz[u] = 1, weight[u] = 0;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;sz[u] += getCentroid(v, u);//找到size最大的子树.weight[u] = max(weight[u], sz[v]);}//子树还有来自父结点的那棵子树.weight[u] = max(weight[u], n - sz[u]);if(weight[u] <= n / 2){centroid[centroid[0] != 0] = u;}return sz[u];
}void getHash(int u, int fa)
{Hash_tree[u] = sz[u] = 1;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;getHash(v, u);sz[u] += sz[v];}for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;Hash_tree[u] = Hash_tree[u] * (Hash[sz[u]] + Hash_tree[v]) % mod;}
}int main()
{for(int i = 1; i < N; i++){Hash[i] = rnd() % mod;}unordered_map<ll, int> Map;scanf("%d", &m);for(int id = 1; id <= m; id++){memset(h, -1, sizeof h);idx = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){int p;scanf("%d", &p);if(!p) continue;add(p, i);add(i, p);}centroid[0] = centroid[1] = 0;getCentroid(1, -1);int rt0 = centroid[0], rt1 = centroid[1];ll res = 1;if(!rt1){getHash(rt0, -1);res = (Hash[sz[rt0]] + Hash_tree[rt0]) % mod;}else{getHash(rt0, rt1);res = (Hash[n] + Hash_tree[rt0]) % mod;getHash(rt1, rt0);res = res * (Hash[n] + Hash_tree[rt1]) % mod;}if(!Map.count(res)) Map[res] = id;printf("%d\\n", Map[res]);}
}

（2） 树和图的宽度优先遍历

847. 图中点的层次

• 给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环。所有边的长度都是 1，点的编号为 $1$∼$n$。请你求出 1 号点到 $n$ 号点的最短距离，如果从 1 号点无法走到 $n$ 号点，输出 −1。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010, maxm = 100010, INF = 0x3f3f3f3f;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, d[maxn];
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {queue<int> que;memset(d, 0x3f, sizeof d);que.push(1);d[1] = 0;while (que.size()) {int u = que.front(); que.pop();for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] != INF) continue;d[v] = d[u] + 1;que.push(v);}}if(d[N] == INF) return -1;return d[N];
}
int main() {scanf("%d%d", &N, &M);memset(h, -1, sizeof h);for (int i = 0; i < M; i++) {int a, b;scanf("%d%d", &a, &b);add(a, b);}bfs();printf("%d\\n", bfs());return 0;
}

最短路问题

（1）Dijkstra朴素算法（O(n2)O(n ^ 2)O(n2)）

• 适用范围：单源最短路，不存在负权边，稠密图。
• 稠密图嘛，用邻接矩阵来存储。
• 还是不乱用memset函数了，一用就错。还是老老实实用for循环吧。
• memset似乎中间可以填的数有：0， -1， 0x3f
• 此方法建图时一定要：g[i, j] =min(g[i, j], cost).
• 小心dij中的第二层循环，总是嵌套错

const int INF = 1e9, maxn = 510;
int G[maxn][maxn], d[maxn], vis[maxn];
int N, M;
int dij(int s, int e) {for (int i = 1; i <= N; i++) d[i] = INF;d[s] = 0;for (int i = 0; i < N; i++) {int t = -1;for (int j = 1; j <= N; j++) {if (!vis[j] && (t == -1 || d[t] > d[j])) t = j;}vis[t] = true;for (int j = 1; j <= N; j++) {d[j] = min(d[j], d[t] + G[t][j]);}}if (d[e] == INF) return -1;return d[e];
}

（2）堆优化版dijkstra （O(mlogn)）

• 适用范围：单源最短路，不存在负权边，稀疏图。

typedef long long ll;
typedef pair<ll, int> P;
const ll INF = 1e16;
int h[maxn], e[maxm], ne[maxm], idx;int vis[maxn], N, M;
ll w[maxm], d[maxn];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = (ll)c, h[a] = idx++;
}
ll dij(int s, int t) {for (int i = 1; i <= N; i++) d[i] = INF;priority_queue<P, vector<P>, greater<P> > que;d[s] = 0;que.push({ 0, 1 });while (que.size()) {P p = que.top(); que.pop();int u = p.second;if (vis[u]) continue;vis[u] = 1;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] > d[u] + w[i]) {d[v] = d[u] + w[i];que.push({ d[v], v });}}}if (d[t] == INF) return -1;return d[t];
}

（3）Bellman-Ford算法（O(nm)）

• 适用范围：单源最短路，存在负权边
• 这个算法几乎用不到，因为可以被spfa取代
• 可以加上限制条件：经过的边不超过k条。若有这个限制的话，即使存在负圈（负权回路），也可以算出最短距离。但是，若无经过边数限制，则一定无最短距离。
• 这道题函数返回的那个地方留意一下，是判断是否大于 INF / 2.
• 再次提醒，图论问题两个易错点：别忘初始化！别弄混边和顶点（N 和 M）！

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];
}

（4）spfa 算法（队列优化的Bellman-Ford算法）

spfa求最短路

• 适用范围：单源最短路，存在负权边（平均情况下O(m)，最坏情况下O(nm)）。
• 这个函数返回值依然是判断是否等于INF，因为这个是用队列维护的，没有更新到的点不会加入队列，自然也不会去更新d[t]的值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010, INF = 0x3f3f3f3f;
int h[maxn], e[maxn], ne[maxn], w[maxn], idx;
int N, M, d[maxn];
bool vis[maxn];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void spfa() {queue<int> que;que.push(1);memset(d, 0x3f, sizeof d);d[1] = 0;vis[1] = true;while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] > d[u] + w[i]) {d[v] = d[u] + w[i];if (!vis[v]) {que.push(v);vis[v] = true;}}}}
}
int main() {scanf("%d%d", &N, &M);memset(h, -1, sizeof h);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}spfa();if (d[N] == INF) printf("impossible\\n");else printf("%d\\n", d[N]);return 0;
}

spfa判断负环

• 注意，从头到尾变化还是不少的
• 原理：统计当前某个点的最短路所包含的边数。若边数大于等于N，则说明有负环。
• 经验表明，spfa求负环的时候，复杂度通常会高达$O(nm)$，那么，经验表明，当所有点入队次数超过2n次的时候，很可能存在负环。虽然不能保证一定正确，但是用spfa超时的时候，这个方法效果还不错。
• d不初始化也无所谓，d的初值并不影响答案。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 2010, maxm = 10010;
int h[maxn], e[maxm], ne[maxm], w[maxm], idx;
int N, M, d[maxn], cnt[maxn];
bool vis[maxn];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
//有负环的话返回true.
bool spfa() {queue<int> que;for (int i = 1; i <= N; i++) {//防止图不连通。其实等效加了一个虚拟超级源点。que.push(i);vis[i] = true;}while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] > d[u] + w[i]) {d[v] = d[u] + w[i];cnt[v] = cnt[u] + 1;if (cnt[v] >= N) return true;if (!vis[v]) {que.push(v);vis[v] = true;}}}}return false;
}
int main() {scanf("%d%d", &N, &M);memset(h, -1, sizeof h);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}if (spfa()) printf("Yes\\n");else printf("No\\n");return 0;
}

（5）floyd算法（O(n3)O(n ^ 3)O(n3)）

• 适用范围：多源最短路，允许有负权边，不能有负环。
• 看看这个怎么初始化的，怎么处理重边与负权边的。
• 应用：最短路，传递闭包，最小环，恰好经过k条边的最短路。

int d[maxn][maxn], N, M, Q;
void flo(){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() {scanf("%d%d%d", &N, &M, &Q);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;}}for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);d[a][b] = min(c, d[a][b]);}flo();while (Q--) {int s, t;scanf("%d%d", &s, &t);//因为存在负权边if (d[s][t] > INF / 2) printf("impossible\\n");else printf("%d\\n", d[s][t]);}return 0;
}

（6）更复杂的最短路问题

Floyd 求最小环：344. 观光之旅

1. 给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。
2. 按照环的编号最大的节点 $k$ 的编号分类。那么环一定可以写成边 $ik$ 、边 $kj$，加上一个路径 $i$ 到 $j$。这样，我们可以确定 $k$ 时，循环所有 $(i,j)$ 对。
3. $d[i,j]=d[i,k]+d[k,j]$，这个 $k$ 就本身具备了记录路径的功能，每当跟新的时候，我们可以把它记录下来，即 $pos[i,j]=k$.
4. 凡是涉及到三个相加的，$INF$ 一定不要写成 $0x3f3f3f3f$，因为又溢出的风险。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 110, INF = 1e7;
int N, M;
int d[maxn][maxn], g[maxn][maxn], cnt, pos[maxn][maxn], ans[maxn];
void get_path(int i, int j) {if (pos[i][j] == 0) return;int k = pos[i][j];get_path(i, k);ans[cnt++] = k;get_path(k, j);
}
int main() {scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) g[i][j] = INF;}for (int i = 1; i <= N; i++) g[i][i] = 0;for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = min(c, g[a][b]);}memcpy(d, g, sizeof d);int res = INF;for (int k = 1; k <= N; k++) {for (int i = 1; i < k; i++) {for (int j = i + 1; j < k; j++) {if (d[i][j] + g[i][k] + g[k][j] < res) {res = d[i][j] + g[j][k] + g[k][i];cnt = 0;ans[cnt++] = k;ans[cnt++] = i;get_path(i, j);ans[cnt++] = j;}}}for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {if (d[i][j] > d[i][k] + d[k][j]) {d[i][j] = d[i][k] + d[k][j];pos[i][j] = k;}}}}if (res == INF) printf("No solution.\\n");else {for (int i = 0; i < cnt; i++) printf("%d ", ans[i]);}return 0;
}

Floyd相关的倍增算法：345. 牛站

• 给定一张由 $T$ 条边构成的无向图，点的编号为 $1\sim 1000$ 之间的整数。求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。

• $floyd$ 算法是 $d[k,i,j]$ 表示从i到j，只经过 $1\sim k$ 的距离最小值。倍增算法略作改动，$d[k,i,j]$ 表示从 $i$ 到 $j$，只经过 $k$ 条边的最短路径。

• 那么，设从 $i$ 到 $k$ 经过 $a$ 条边，从 $k$ 到 $j$ 经过 $b$ 条边，那么 $d[a+b,i,j]=\min (d[a,i,k]+d[b,k,j])$。

• 注意，sizeof参数必须是一个真正的数组，不可以是函数传进来的指针

• 复杂度是O(n3log⁡n)O(n^3 \\log n)O(n3logn)。运用了快速幂的思想。快速幂可以成立的一个重要原因是结合律是成立的。包括矩阵的快速幂也是因为矩阵之间乘法的结合律是成立的。具体的解释可以看看代码注释：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 110, INF = 0x3f3f3f3f;
int g[maxn][maxn], res[maxn][maxn];
int N, M, K, st, ed;
map<int, int> id;void mul(int c[][maxn], int a[][maxn], int b[][maxn]) {//因为c与a或b可能是同一数组，防止访问冲突，再开一个数组。static int tmp[maxn][maxn];for (int i = 0; i < maxn; i++) fill(tmp[i], tmp[i] + maxn, INF);for (int k = 0; k < N; k++) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]);}}}//这一步其实相当于重新建图，把经过边数为1的路径去掉，把边数为2的路径作为新的边连起来。memcpy(c, tmp, sizeof tmp);
}
void qmi() {for (int i = 0; i < maxn; i++) {fill(res[i], res[i] + maxn, INF);//这个地方必须要把res[i][i]初始化为0.因为这个存的是答案，不只是路径的问题。res[i][i] = 0;}//就像快速幂一样。while (K) {//mul(res, res, g) 和 mul(res, g, res) 都可以 ACif (K & 1) mul(res, res, g);mul(g, g, g);K >>= 1;}
}
int main() {scanf("%d%d%d%d", &K, &M, &st, &ed);if (!id.count(st)) id[st] = N++;st = id[st];if (!id.count(ed)) id[ed] = N++;ed = id[ed];for (int i = 0; i < maxn; i++) {fill(g[i], g[i] + maxn, INF);}//注意，这里不可以把g[i][i]初始化为0.因为从i走到i表示一个自环呀，算经过1个节点。for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &c, &a, &b);if (!id.count(a)) id[a] = N++;if (!id.count(b)) id[b] = N++;a = id[a], b = id[b];g[a][b] = g[b][a] = min(g[a][b], c);}qmi();printf("%d\\n", res[st][ed]);return 0;
}

• 其实还可以这样写倍增算法：

void qmi() {memset(res, 0x3f, sizeof res);for (int i = 1; i <= N; i++) res[i][i] = 0;while (K) {//差别在这里，把结果存在res里面，这样更像快速幂。//而且此时写成mul(g, res, res)不影响结果。感觉这样子好像更合理一些。if (K & 1) mul(res, g, res);mul(g, g, g);K >>= 1;}
}

外部拓扑排序+内部dijkstra：342. 道路与航线

• 可以分块。块儿内部都是非负权边，可以用dijkstra来算。团外部又负权边但是无环，可以按照拓扑图来做。块儿的内部是不可能有航线的。因为若A和B节点之间有航线，就不可能有道路，否则无法满足“不能从B到A”这一条件。
• 另外，我在想，最开始的时候，如果一个连通块入度为0，是不是等价于S在这个连通块儿内部。不然，这个连通块儿是不可能从S走的到的呀。
• 当然要入度减到0的时候入队啊，不然其他的点根本就没办法用dijkstra计算啊。
• 最后还是要提醒，又负权边的话，只要不是 spfa，最后判断距离都要 > INF / 2。

1. 先输入所有双向道路,然后 DFS 出所有连通块，计算两个数组: id[] 存储每个点属于哪个连通块; vector< int > block[] 存储每个连通块里有哪些点;
2. 输入所有航线，同时统计出每个连通块的入度。
3. 按照拓扑序依次处理每个连通块。先将所有入度为0的连通块的编号加入队列中。
4. 每次从队头取出一个连通块的编号bid.
5. 将该block[bid]中的所有点加入堆中，然后对堆中所有点跑dijkstra算法。注：这相当于建立了超级源点（即起点），然后将该块中的所有点都加入队列中.
6. 每次取出堆中距离最小的点ver.
7. 然后遍历ver的所有邻点。如果 $id[ver]==id[j]$，那么如果 $j$ 能被更新，则将其插入堆中；如果 $id[ver]\ne id[j]$ ，则将 $id[j]$ 这个连通块的入度减 $1$，如果减成 $0$了，则将其插入拓扑排序的队列中。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 25010, maxm = 150010, INF = 0x3f3f3f3f;
int h[maxn], e[maxm], ne[maxm], w[maxm], idx;
int N, M1, M2, S, d[maxn];
bool vis[maxn];
int id[maxn], in[maxn], bcnt;
vector<int> blocks[maxn];
void add(int a, int b, int c){e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
queue<int> que;
void dfs(int u) {blocks[bcnt].push_back(u);id[u] = bcnt;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (!id[v]) dfs(v);}
}
typedef pair<int, int> P;
void dijkstra(int x) {priority_queue<P, vector<P>, greater<P> > pq;for (auto u : blocks[x]) pq.push(P(d[u], u));while (pq.size()) {auto p = pq.top(); pq.pop();int u = p.second, dis = p.first;if (vis[u]) continue;vis[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] > d[u] + w[i]) {d[v] = d[u] + w[i];if (id[u] == id[v]) pq.push(P(d[v], v));}if (id[u] != id[v] && --in[id[v]] == 0) que.push(id[v]);}}
}
void toposort() {fill(d, d + maxn, INF);for (int i = 1; i <= bcnt; i++) {if (in[i] == 0) que.push(i);}d[S] = 0;while (que.size()) {int x = que.front(); que.pop();dijkstra(x);}
}
int main() {memset(h, -1, sizeof h);scanf("%d%d%d%d", &N, &M1, &M2, &S);for (int i = 0; i < M1; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}for (int i = 1; i <= N; i++) {if (!id[i]) {bcnt++;dfs(i);}}for (int i = 0; i < M2; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);in[id[b]]++;}toposort();for (int i = 1; i <= N; i++) {if (d[i] > INF / 2) printf("NO PATH\\n");else printf("%d\\n", d[i]);}return 0;
}

活用spfa：341. 最优贸易

• 题意：$n$ 个点 $m$ 条边，任意两个点之间至多一条道路，有单向边也有双向边，每个点都有一个点权，要求找到两个结点 $u$ 和 $v$，使得 $u$ 的点权 减去$v$ 的点权的结果最大，并且可以从1号点走到 $u$，从 $u$ 走到 $v$，再从 $v$ 走到 $n$ 号点.
• 这个可以从 $dp$ 的角度思考问题。以 $k$ 为分界点，买在 $1\sim k$ 中（在这之间寻找买入最小值 $dmin[k]$ ），卖在 $k\sim N$ 中（在这之间寻找卖出最大值 $dmax[k]$），不过这里的 $k$ 也可以作为买入点或卖出点。
• 记 $F[x]$ 为点权，$D[x]$ 存储从起点到 $x$ 的访问到的点权的最大值或最小值。建图以及建反图，可以用 SPFA 或者 Dijkstra 算法，把 $d[x]+w(x,y)$ 换成 d[x]=min⁡{d[x],price[y]}d[x] = \\min\\{d[x],price[y]\\}d[x]=min{d[x],price[y]} 来更新。正反分别跑一遍最短路；最后枚举每个节点 $x$，用 $F[x]-D[x]$ 更新答案。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 100010, maxm = 2000010, INF = 0x3f3f3f3f;
int hs[maxn], ht[maxn], e[maxm], ne[maxm], w[maxn], idx;
int dmin[maxn], dmax[maxn], N, M;
bool vis[maxn];
void add(int a, int b, int type) 
{if (type) e[idx] = b, ne[idx] = ht[a], ht[a] = idx++;else e[idx] = b, ne[idx] = hs[a], hs[a] = idx++;
}
void spfa(int h[], int d[], int type) 
{queue<int> que;//spfa是不用将vis初始化的。因为队列为空的时候才会跳出while循环嘛。if (!type) {fill(d, d + maxn, INF);d[1] = w[1], vis[1] = true;que.push(1);}else {//这一步将d初始化为0或-INF都是对的。因为点权的最小值是1。//一开始我还以为是边权变成负数然后求最大值，然后发现不是这样。//因为这个不是在跑最短路，只是用了spfa的板子而已。fill(d, d + maxn, -INF);d[N] = w[N], vis[N] = true;que.push(N);}while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (!type && d[v] > min(d[u], w[v]) || type && d[v] < max(d[u], w[v])) {if (!type) d[v] = min(d[u], w[v]);else d[v] = max(d[u], w[v]);if (!vis[v]) {vis[v] = true;que.push(v);}}}}
}
int main() {memset(hs, -1, sizeof hs);memset(ht, -1, sizeof ht);scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) scanf("%d", &w[i]);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, 0), add(b, a, 1);if (c == 2) add(b, a, 0), add(a, b, 1);}spfa(hs, dmin, 0);spfa(ht, dmax, 1);int ans = 0;for (int i = 1; i <= N; i++) ans = max(dmax[i] - dmin[i], ans);printf("%d\\n", ans);return 0;
}

拆点（分层图）：1131. 拯救大兵瑞恩

• 题意：整个迷宫被划分为 $n\ast m$ 个单元。南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，同一个单元可能存放多把钥匙，并且所有的门被分成 $P$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。求从 $(1,1)$出发 到 $(n,m)$ 的最少移动距离。

• $1\le n,m,p\le 10$，墙和门的总数最多150个.

• 从 $dp$ 角度思考，设 $d(x,y,state)$ 就是在 $(x,y)$ 这个点，拥有钥匙状态时 $state$ (因为只有10把钥匙🔑，所以用二进制表示很方便)，这个值储存的是最短步数。可以变成两种情况：

1. 捡钥匙：d(x,y,state)=min⁡{d(x,y,state),d(x,y,state∣key)}d(x, y, state) = \\min\\{d(x, y, state), d(x, y, state | key)\\}d(x,y,state)=min{d(x,y,state),d(x,y,state∣key)}；
2. 移动（没有门或墙，有门且有匹配的钥匙）：d(a,b,state)=max⁡{d(x,y,state)+1,d(a,b,state)}d(a, b, state) = \\max\\{d(x, y, state) + 1, d(a, b, state)\\}d(a,b,state)=max{d(x,y,state)+1,d(a,b,state)}。

• 所以状态的转移可以是走 $1$ 步，也可以是走 $0$ 步。就可以变成双端队列广搜了。于是处理步骤如下：

1. 建图：先把墙和门的信息保存在 $set$ 里面，然后用邻接表建图。用 $w[i]$ 表示边的信息，$0$ 为没有门也没有墙，$>0$ 时为需要哪个钥匙，这里多说一句，输入0时表示有墙，但是有墙的时候是不建立边的。
2. 先捡钥匙，此过程就是走权重为 $0$ 的边。第二步向四个方向移动，就是走权重为 $1$ 的边。然后答案就出来了。

• 小心左移右移别搞混。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<set>
using namespace std;
const int maxn = 110, maxm = 410, maxp = 1 << 10, INF = 0x3f3f3f3f;
int h[maxn], e[maxm], ne[maxm], w[maxm], idx;
bool vis[maxn][maxp];
typedef pair<int, int> P;
set<P> s;
int g[15][15], N, M, T, K, S, key[maxn], d[maxn][maxp];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
deque<P> dq;
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
void build() {for (int x = 1; x <= N; x++) {for (int y = 1; y <= M; y++) {for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 1 || nx > N || ny < 1 || ny > M) continue;int a = g[x][y], b = g[nx][ny];//没有墙或门，则记边权为0。if (!s.count(P(a, b))) add(a, b, 0);}}}
}
int bfs() {for (int i = 1; i <= N * M; i++) {fill(d[i], d[i] + maxp, INF);}d[1][0] = 0;dq.push_back(P(1, 0));while (dq.size()) {auto p = dq.front(); dq.pop_front();int u = p.first, state = p.second;if (vis[u][state]) continue;vis[u][state] = true;if (u == N * M) return d[u][state];if (key[u]) {int new_state = state | key[u];if (d[u][new_state] > d[u][state]) {d[u][new_state] = d[u][state];dq.push_front(P(u, new_state));}}for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v][state] > d[u][state] + 1) {if (w[i] && !((state >> w[i] - 1) & 1)) continue;d[v][state] = d[u][state] + 1;dq.push_back(P(v, state));}} }return -1;
}
int main() {memset(h, -1, sizeof h);int id = 1;scanf("%d%d%d%d", &N, &M, &T, &K);for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) g[i][j] = id++;}for (int i = 0; i < K; i++) {int x1, y1, x2, y2, c;scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);int a = g[x1][y1], b = g[x2][y2];s.insert(P(a, b)), s.insert(P(b, a));if (c) add(a, b, c), add(b, a, c);}scanf("%d", &S);for (int i = 0; i < S; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);int u = g[a][b];key[u] |= 1 << c - 1;}build();printf("%d\\n", bfs());return 0;
}