最短路问题（2025暑假集训）

## 7.28 dijkstra （Dijkstra's Algorithm）
时间复杂度$O(mlogm)$
### dijkstra 模版
```cpp
void dijkstra(int bg)
{
	priority_queue<P, vector, greater> heap;
	memset (dist, 0x3f, sizeof(dist));
	heap.push({0, bg});
	dist[bg] = 0;
	while (!heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		if (st[t.second]) continue;
		st[t.second] = true;
		for (auto [u, v] : vec[t.second])
		{
			int j = u;
			if (dist[j] > dist[t.second] + v)
			{
				dist[j] = dist[t.second] + v;
				heap.push({dist[j], j});
			}
		}
	}
	return;
}
```
### 练习01 [洛谷P4779 单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
~~模版题，思路不说了，直接上代码\~~~ 
这个题一个朴素的 $O(mlogm)$ 级别的 dijkstra 轻松拿捏~
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int inf = 1061109567;
const int N = 1e5 + 10;

int n, m, s, dist[N], a, b, c;
vector <pair<int, int>> vec[N];
bool st[N];

void dijkstra(int bg)
{
	priority_queue<P, vector, greater> heap;
	memset (dist, 0x3f, sizeof(dist));
	heap.push({0, bg});
	dist[bg] = 0;
	while (!heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		if (st[t.second]) continue;
		st[t.second] = true;
		for (auto p : vec[t.second])
		{
			int j = p.first;
			if (dist[j] > dist[t.second] + p.second)
			{
				dist[j] = dist[t.second] + p.second;
				heap.push({dist[j], j});
			}
		}
	}
	return;
}

signed main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; ++ i)
	{
		cin >> a >> b >> c;
		vec[a].push_back({b, c});
	}
	dijkstra(s);
	for (int i = 1; i <= n; ++ i) cout << dist[i] << ' ';

return 0;
}
```
### 练习02 [洛谷P2910 [USACO08OPEN] Clear And Present Danger S](https://www.luogu.com.cn/problem/P2910)
这个题两个要点：
> 1. 其实不必理会“从 $1$ 号小岛到 $N$ 号小岛”
> 2. 注意读入！！！
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int inf = 1061109567;
const int N = 100 + 10;
const int M = 1e4 + 10;

int n, m, arr[M], dist[N], a, res;
vector vec[N];
bool st[N];

void dijkstra(int bg)
{
	priority_queue<P, vector, greater> heap;
	memset (dist, 0x3f, sizeof(dist));
	memset (st, false, sizeof(st));
	heap.push({0, bg});
	dist[bg] = 0;
	while (!heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		if (st[t.second]) continue;
		st[t.second] = true;
		for (auto p : vec[t.second])
		{
			int j = p.first;
			if (dist[j] > dist[t.second] + p.second)
			{
				dist[j] = dist[t.second] + p.second;
				heap.push({dist[j], j});
			}
		}
	}
	return;
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) cin >> arr[i];
	for (int i = 1; i <= n; ++ i)
	{
		for (int j = 1; j <= n; ++ j)
		{
			cin >> a;
			if (j == i) continue;
			vec[i].push_back({j, a});
		}
	}
	for (int i = 1; i < m; ++ i)
	{
		dijkstra(arr[i]);
		res += dist[arr[i + 1]];
	}
	cout << res << endl;

return 0;
}
```
### 练习03 [洛谷P1396 营救](https://www.luogu.com.cn/problem/P1396)
二分答案+`dfs`/`bfs`查联通块
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int inf = 1061109567;
const int N = 1e4 + 10;

int n, m, s, t, a, b, c, l, r, mid, ans;
vector vec[N];
vector <int> edge[N];
bool st[N];

bool check(int x)
{
	for (int i = 1; i <= n; ++ i) edge[i].clear();
	memset (st, false, sizeof(st));
	for (int i = 1; i <= n; ++ i)
	{
		for (auto j : vec[i])
		{
			int w = j.second;
			if (w <= x) edge[i].push_back(j.first);
		}
	}
	queue <int> q;
	st[s] = true;
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (auto xx : edge[x])
		{
			if (!st[xx])
			{
				q.push(xx);
				st[xx] = true;
			}
		}
	}
	return st[t];
}

signed main()
{
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; ++ i)
	{
		cin >> a >> b >> c;
		vec[a].push_back({b, c});
		vec[b].push_back({a, c});
		r = max(r, c);
	}
	while (l <= r)
	{
		mid = l + (r - l) / 2;
		if (check(mid))
		{
			r = mid - 1;
			ans = mid;
		}
		else l = mid + 1;
	}
	cout << ans << endl;

return 0;
}
```

### 作业 [洛谷P1576 最小花费](https://www.luogu.com.cn/problem/P1576)

## 7.29 SPFA（Shortest Path Faster Algorithm）
贝尔曼-福德（Bellman-Ford）要先判断**负环**！（有负环求不了最短路）
### Bellman-Ford 模板
```cpp
void bellman_ford()
{
 bk[s] = 0;
 for (int i = 1; i < n; ++ i)
 {
 memcpy(dist, bk, sizeof(dist));
 for (int j = 1; j <= m; ++ j)
 {
 if (dist[v] > dist[u] + w) bk[v] = bk[u] + w;
 }
 }
 return;
}
```
### SPFA 模板
```cpp
bool spfa() // 判负环
{
 queue <int> q;
 memset(dist, 0x3f, sizeof(dist));
 memset(cnt, 0, sizeof(cnt));
 memset(st, false, sizeof(st));
 for (int i = 1; i <= n; ++ i)
 {
 q.push(i);
 st[i] = true;
 }
 dist[1] = 0;
 while (!q.empty())
 {
 auto a = q.front();
 q.pop();
 st[a] = false;
 for (auto [v, w] : vec[a])
 {
 int j = v;
 if (dist[j] > dist[a] + w[i])
 {
 dist[j] = dist[a] + w[i];
 cnt[j] = cnt[a] + 1;
 if (cnt[j] >= n) return true;
 if (!st[j])
 {
 st[j] = true;
 q.push(j);
 }
 }
 }
 }
 return false;
}

void spfa() // 正常食用
{
 queue <int> q;
 memset(dist, 0x3f, sizeof(dist));
 memset(st, false, sizeof(st));
 for (int i = 1; i <= n; ++ i)
 {
 q.push(i);
 st[i] = true;
 }
 dist[1] = 0;
 while (!q.empty())
 {
 auto a = q.front();
 q.pop();
 st[a] = false;
 for (auto [v, w] : vec[a])
 {
 int j = v;
 if (dist[j] > dist[a] + w[i])
 {
 dist[j] = dist[a] + w[i];
 if (!st[j])
 {
 st[j] = true;
 q.push(j);
 }
 }
 }
 }
 return;
}
```
### 练习04 [洛谷P3385【模板】负环](https://www.luogu.com.cn/problem/P3385)
使用上面`SPFA`判负环模板即可\~ 
注意**多测**和**输入**
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 2e3 + 10;

int t, n, m, u, v, w, dist[N], cnt[N];
vector vec[N];
bool st[N];

bool spfa() // 判负环
{
 queue <int> q;
 memset(dist, 0x3f, sizeof(dist));
 memset(cnt, 0, sizeof(cnt));
 memset(st, false, sizeof(st));
// for (int i = 1; i <= n; ++ i)
// {
// q.push(i);
// st[i] = true;
// }
 q.push(1);
 dist[1] = 0;
 st[1] = true;
 while (!q.empty())
 {
 auto a = q.front();
 q.pop();
 st[a] = false;
 for (auto [v, w] : vec[a])
 {
 int j = v;
 if (dist[j] > dist[a] + w)
 {
 dist[j] = dist[a] + w;
 cnt[j] = cnt[a] + 1;
 if (cnt[j] >= n) return true;
 if (!st[j])
 {
 st[j] = true;
 q.push(j);
 }
 }
 }
 }
 return false;
}

signed main()
{
 cin >> t;
 while (t)
 {
 cin >> n >> m;
 for (int i = 1; i <= n; ++ i) vec[i].clear();
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 if (w >= 0)
 {
 vec[u].push_back({v, w});
 vec[v].push_back({u, w});
 }
 else vec[u].push_back({v, w});
 }
 if (spfa()) cout << "YES" << endl;
 else cout << "NO" << endl;
 -- t;
 }

return 0;
}

```
### 练习05 [洛谷P2850 [USACO06DEC] Wormholes G](https://www.luogu.com.cn/problem/P2850)
将题目转化成有没有负环即可 
注意**输入**
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 800;

int t, n, m, k, u, v, w, dist[N], cnt[N];
bool st[N];
vector vec[N];

bool spfa() // 判负环
{
 queue <int> q;
 memset(dist, 0x3f, sizeof(dist));
 memset(cnt, 0, sizeof(cnt));
 memset(st, false, sizeof(st));
 for (int i = 1; i <= n; ++ i)
 {
 q.push(i);
 st[i] = true;
 dist[i] = 0;
 }
 while (!q.empty())
 {
 auto a = q.front();
 q.pop();
 st[a] = false;
 for (auto [v, w] : vec[a])
 {
 int j = v;
 if (dist[j] > dist[a] + w)
 {
 dist[j] = dist[a] + w;
 cnt[j] = cnt[a] + 1;
 if (cnt[j] >= n) return true;
 if (!st[j])
 {
 st[j] = true;
 q.push(j);
 }
 }
 }
 }
 return false;
}

void solve()
{
 cin >> n >> m >> k;
 for (int i = 1; i <= n; ++ i) vec[i].clear();
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 vec[u].push_back({v, w});
 vec[v].push_back({u, w});
 }
 for (int i = 1; i <= k; ++ i)
 {
 cin >> u >> v >> w;
 vec[u].push_back({v, -w});
 }
 if (spfa()) cout << "YES" << endl;
 else cout << "NO" << endl;
}

signed main()
{
    cin >> t;
    while (t)
    {
        solve();
        -- t;
    }

return 0;
}

```
### 作业 [洛谷P1073 [NOIP 2009 提高组] 最优贸易](https://www.luogu.com.cn/problem/P1073)
**分层图** 
买 $-w$ 
卖 $w$ 
同层权值为 $0$ 
求最长路即可
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 3e5 + 10;

int n, a[N], m, u, v, w, dist[N], res = -inf;
bool st[N];
vector vec[N];

void spfa()
{
 queue <int> q;
 memset(dist, 0x3f, sizeof(dist));
 memset(st, false, sizeof(st));
 q.push(1);
 dist[1] = 0;
 st[1] = true;
 while (!q.empty())
 {
 auto a = q.front();
 q.pop();
 st[a] = false;
 for (auto p : vec[a])
 {
 int j = p.first;
 if (dist[j] > dist[a] + p.second)
 {
 dist[j] = dist[a] + p.second;
 if (!st[j])
 {
 st[j] = true;
 q.push(j);
 }
 }
 }
 }
 return;
}

signed main()
{
 cin >> n >> m;
 for (int i = 1; i <= n; ++ i) cin >> a[i];
 for (int i = 1; i <= n; ++ i)
 {
 vec[i].push_back({n + i, a[i]});
 vec[n + i].push_back({2 * n + i, - a[i]});
 }
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 if (w == 1)
 {
 vec[u].push_back({v, 0});
 vec[n + u].push_back({n + v, 0});
 vec[2 * n + u].push_back({2 * n + v, 0});
 }
 else
 {
 vec[u].push_back({v, 0});
 vec[n + u].push_back({n + v, 0});
 vec[2 * n + u].push_back({2 * n + v, 0});
 vec[v].push_back({u, 0});
 vec[n + v].push_back({n + u, 0});
 vec[2 * n + v].push_back({2 * n + u, 0});
 }
 }
 spfa();
 cout << - dist[3 * n] << endl;

return 0;
}

```
## 7.30 Floyd（Floyd-Warshall‘s Algorithm）
```cpp
dp[i][j] // 从 i 到 j 的最短路
dp[1][n] // 答案
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); // 转移
memset(dp, 0x3f, sizeof(dp));
dp[i][i] = 0;
dp[i][j] = w; // 有一条 i 到 j 权值为 w 的边
```
### Floyd 模版
时间复杂度 $O(n ^ 3)$
```cpp
void floyd(int x, int y)
{
 for (int k = 1; k <= n; ++ k)
 {
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
 }
 }
}

```
### 练习06 [B3647【模板】Floyd](https://www.luogu.com.cn/problem/B3647)
注意有**重边**！！！
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int inf = 1061109567;
const int N = 100 + 10;

int n, m, dp[N][N], u, v, w;

signed main()
{
 cin >> n >> m;
 memset (dp, 0x3f, sizeof(dp));
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 dp[u][v] = dp[v][u] = min(dp[u][v], w);
 }
 for (int i = 1; i <= n; ++ i) dp[i][i] = 0;
 for (int k = 1; k <= n; ++ k)
 {
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
 }
 }
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j)
 {
 if (i == j) cout << 0 << ' ';
 else cout << dp[i][j] << ' ';
 }
 cout << endl;
 }

return 0;
}

```
### 练习07 [洛谷P1522 [USACO2.4] 牛的旅行 Cow Tours](https://www.luogu.com.cn/problem/P1522)
两点之间距离 $\sqrt{{|x_1-x_2|}^2+{|y_1-y_2|}^2}$ 
前人的经验：注意**代码细节**！！！~~（ `WA` 了 $8$ 次。。。）~~
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;
using ll = long long;

const int inf = 1061109567;
const double DINF = 1e18;
const int N = 160;

int n, u, v, fa[N];
double g[N][N], d[N], dd[N];
P p[N];

signed main()
{
 cin >> n;
 for (int i = 1; i <= n; ++ i)
 {
 cin >> u >> v;
 p[i] = make_pair(u, v);
 }
 auto gdist = [&](int i, int j) -> double
 {
 auto sqr = [&](ll x) -> ll
 {
 return x * x;
 };
 return sqrtl(sqr(p[i].first - p[j].first) + sqr(p[i].second - p[j].second));
 };
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j)
 {
 char c;
 cin >> c;
 if (c == '1') g[i][j] = gdist(i, j);
 else g[i][j] = DINF;
 }
 }
 for (int k = 1; k <= n; ++ k)
 {
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
 }
 }
 double ans = DINF;
 for (int i = 1; i <= n; ++ i)
 {
 double res = 0;
 for (int j = 1; j <= n; ++ j)
 {
 if (i == j) continue;
 if (g[i][j] == DINF) continue;
 res = max(g[i][j], res);
 }
 d[i] = res;
 // cerr << d[i] << ' ';
 // ans = max(res, ans);
 }
 for (int i = 1; i <= n; ++ i)
 {
 if (fa[i]) continue;
 dd[i] = d[i];
 fa[i] = i;
 for (int j = i + 1; j <= n; ++ j)
 {
 if (g[i][j] == DINF || fa[j]) continue;
 fa[j] = i;
 dd[i] = max(dd[i], d[j]);
 }
 }
 // cerr << endl;
 for (int i = 1; i <= n; ++ i)
 {

for (int j = i + 1; j <= n; ++ j)
 {
 if (g[i][j] != DINF) continue;
 ans = min(ans, max({gdist(i, j) + d[i] + d[j], dd[fa[i]], dd[fa[j]]}));
 }
 }
 cout << fixed << setprecision(6) << ans << endl;

return 0;
}

```
### 传递闭包
```cpp
bool g[i][j];
for (int k = 1; k <= n; ++ k)
{
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j) g[i][j] |= g[i][k] & g[k][j];
 }
}
```
### 练习08 [洛谷P2419 [USACO08JAN] Cow Contest S](https://www.luogu.com.cn/problem/P2419)
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int inf = 1061109567;
const int N = 100 + 10;

int n, m, a, b, res;
bool f[N][N];

signed main()
{
 cin >> n >> m;
 for (int i = 1; i <= m; ++ i)
 {
 cin >> a >> b;
 f[a][b] = true;
 }
 for (int k = 1; k <= n; ++ k)
 {
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j) f[i][j] |= f[i][k] & f[k][j];
 }
 }
 for (int i = 1; i <= n; ++ i)
 {
 bool flag = true;
 for (int j = 1; j <= n; ++ j)
 {
 if (i == j) continue;
 if (!f[i][j] && !f[j][i]) flag = false;
 }
 if (flag) ++ res;
 }
 cout << res << endl;
 // for (int i = 1; i <= n; ++ i)
 // {
 // for (int j = 1; j <= n; ++ j) cout << f[i][j] << ' ';
 // cout << endl;
 // }

return 0;
}

```
### 作业 [洛谷P1119 灾后重建](https://www.luogu.com.cn/problem/P1119)
在使用 `Floyd` $O(n ^ 3)$ 处理完前 $n$ 个点后，在处理第 $n + 1$ 个点时，跑 $O(n ^ 2)$ 的 `dp` 即可，不必 $O(n ^ 3)$ 跑 `Floyd` 。
## 7.31 最短路特殊建图
### 练习09 [洛谷P5764 [CQOI2005] 新年好](https://www.luogu.com.cn/problem/P5764)
瞅一眼就知道，这题是个 `dijkstra` 
注意题目没说顺序，全排列 `next_permutation()`
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 5e4 + 10;

int n, m, a[N], u, v, w, dist[10][N], ans = 0, res = inf;
bool st[N];
vector vec[N];
map <int, int> mp;

void dijkstra(int bg)
{
 priority_queue <P, vector, greater> heap;
 memset (st, false, sizeof(st));
 heap.push({0, bg});
 dist[mp[bg]][bg] = 0;
 while (!heap.empty())
 {
 auto t = heap.top();
 heap.pop();
 if (st[t.second]) continue;
 st[t.second] = true;
 for (auto it : vec[t.second])
 {
 int j = it.first;
 if (dist[mp[bg]][j] > dist[mp[bg]][t.second] + it.second)
 {
 dist[mp[bg]][j] = dist[mp[bg]][t.second] + it.second;
 heap.push({dist[mp[bg]][j], j});
 }
 }
 }
 return;
}

signed main()
{
 memset (dist, 0x3f, sizeof(dist));
 cin >> n >> m;
 a[0] = 1;
 mp[a[0]] = 0;
 for (int i = 1; i <= 5; ++ i)
 {
 cin >> a[i];
 mp[a[i]] = i;
 }
 sort (a, a + 6);
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 vec[u].push_back(make_pair(v, w));
 vec[v].push_back(make_pair(u, w));
 }
 for (int i = 0; i <= 5; ++ i) dijkstra(a[i]);
 // for (int i = 0; i <= 5; ++ i)
 // {
 // for (int j = 1; j <= n; ++ j) cout << dist[i][j] << ' ';
 // cout << endl;
 // }
 do
 {
 // cout << s << endl;
 ans = 0;
 for (int i = 0; i < 5; ++ i) ans += dist[mp[a[i]]][a[i + 1]];
 // cout << ans << ' ';
 res = min(res, ans);
 // cout << ans << endl;
 } while (next_permutation (a + 1, a + 6));
 cout << res << endl;

return 0;
}

```
### 练习10 [洛谷P1948 [USACO08JAN] Telephone Lines S](https://www.luogu.com.cn/problem/P1948)
~~emm 集训的第 $2$ 道蓝题。。。~~

二分 + `dijkstra` 
~~然后我发现我的 `check` 不会写~~ 
`check` 函数很简单，将长度 $\le$ `mid` 的权值设为 $0$ ， $>$ `mid` 的权值设为 $1$ ， `dijkstra` 或 `deque` 即可
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 1e3 + 10;
const int M = 1e4 + 10;

int l, r, mid, ans = -1, n, m, k, u[M], v[M], w[M], dist[N];
bool st[N];
vector edge[N];

void dijkstra(int bg)
{
 priority_queue<P, vector, greater> heap;
 memset (dist, 0x3f, sizeof(dist));
 memset (st, false, sizeof(st));
 heap.push({0, bg});
 dist[bg] = 0;
 while (!heap.empty())
 {
 auto t = heap.top();
 heap.pop();
 if (st[t.second]) continue;
 st[t.second] = true;
 for (auto p : edge[t.second])
 {
 int j = p.first;
 if (dist[j] > dist[t.second] + p.second)
 {
 dist[j] = dist[t.second] + p.second;
 heap.push({dist[j], j});
 }
 }
 }
 return;
}

bool check(int x)
{
 for (int i = 1; i <= n; ++ i) edge[i].clear();
 for (int i = 1; i <= m; ++ i)
 {
 if (w[i] <= x) 
 {
 edge[u[i]].push_back({v[i], 0});
 edge[v[i]].push_back({u[i], 0});
 }
 else
 {
 edge[u[i]].push_back({v[i], 1});
 edge[v[i]].push_back({u[i], 1});
 }
 }
 dijkstra(1);
 if (dist[n] > k) return false;
 return true;
}

signed main()
{
 cin >> n >> m >> k;
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u[i] >> v[i] >> w[i];
 r = max (r, w[i]);
 }
 while (l <= r)
 {
 mid = l + (r - l) / 2;
 if (check(mid))
 {
 ans = mid;
 r = mid - 1;
 }
 else l = mid + 1;
 }
 cout << ans << endl;

return 0;
}

```
### 作业 [洛谷P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)
**分层图** ： $k$ 条边免费，即 $k + 1$ 层图，同图中边权为 $w$ ，不同图边权为 $0$ 。
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 2e5 + 10;

int n, m, k, s, t, u, v, w, dist[N];
bool st[N];
vector vec[N];

void dijkstra(int bg)
{
 priority_queue <P, vector, greater> heap;
 memset (dist, 0x3f, sizeof(dist));
 heap.push({0, bg});
 dist[bg] = 0;
 while (!heap.empty())
 {
 auto t = heap.top();
 heap.pop();
 if (st[t.second]) continue;
 st[t.second] = true;
 for (auto p : vec[t.second])
 {
 int j = p.first;
 if (dist[j] > dist[t.second] + p.second)
 {
 dist[j] = dist[t.second] + p.second;
 heap.push({dist[j], j});
 }
 }
 }
 return;
}

signed main()
{
 cin >> n >> m >> k;
 cin >> s >> t;
 ++ s;
 ++ t;
 t += k * n;
 for (int i = 1; i <= m; ++ i)
 {
 cin >> u >> v >> w;
 ++ u;
 ++ v;
 for (int j = 0; j <= k; ++ j)
 {
 vec[u + j * n].push_back({v + j * n, w});
 vec[v + j * n].push_back({u + j * n, w});
 }
 for (int j = 0; j < k; ++ j)
 {
 vec[u + j * n].push_back({v + j * n + n, 0});
 vec[v + j * n].push_back({u + j * n + n, 0});
 }
 }
 dijkstra(s);
 // for (int i = 1; i <= (k + 1) * n; ++ i) cout << dist[i] << ' ';
 cout << (k >= m ? 0 : dist[t]) << endl;

return 0;
}

```
## 8.1 最小生成树（Kruskal Algorithm）
原始算法： `Brouka`  
`kruskal` ： $O(mlogm)$ （基于并查集）  
`prim` ： $O(n ^ 2)$  
~~So, what's `最小生成树` ?~~  
树的判定：**联通**的图，且有 $n$ 个点， $n - 1$ 条边  
基环树：有以环上的点为根的树的图  
基环树处理方法：断环上的边  
算法实现：
> 对边排序
> 从小到大选边（如果在同一集合中，不连边）
> 最多选 $n - 1$ 条边
### 模版
```cpp
int _find (int x)
{
    if (fa[x] != x) fa[x] = _find(fa[x]);
    return fa[x];
}

struct node
{
 int u, v, w;
 bool operator < (const node & t)
 const
 {
 return w < t.w;
 }
} edge[N] ;

void kruskal()
{
 sort (edge + 1, edge + n + 1);
 for (auto i : edge)
 {
 int a = i.u;
 int b = i.v;
 int c = i.w;
 if (_find(a) != _find(b))
 {
 ++ cnt;
 ans += c;
 fa[_find(a)] = _find(b);
 }
 }
 return ans;
}
```
### 练习11 [洛谷P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int inf = 1061109567;
const int N = 5016;
const int M = 2e5 + 10;

int n, m, a, b, c, fa[N], cnt, ans;

int _find (int x)
{
    if (fa[x] != x) fa[x] = _find(fa[x]);
    return fa[x];
}

struct node
{
 int u, v, w;
 bool operator < (const node & t)
 const
 {
 return w < t.w;
 }
} edge[M] ;

signed main()
{
 cin >> n >> m;
 for (int i = 1; i <= n; ++ i) fa[i] = i;
 for (int i = 1; i <= m; ++ i)
 {
 cin >> a >> b >> c;
 edge[i] = {a, b, c};
 }
 sort (edge + 1, edge + m + 1);
 for (int i = 1; i <= m; ++ i)
 {
 int a = edge[i].u;
 int b = edge[i].v;
 int c = edge[i].w;
 if (_find(a) != _find(b))
 {
 ++ cnt;
 ans += c;
 fa[_find(a)] = _find(b);
 }
 }
 if (cnt == n - 1) cout << ans << endl;
 else cout << "orz" << endl;

return 0;
}

```
### 练习12 [洛谷P1546 [USACO3.1] 最短网络 Agri-Net](https://www.luogu.com.cn/problem/P1546)
最小生成树即可
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int inf = 1061109567;
const int N = 1e4 + 10;

int n, a, b, c, fa[N], ans;

int _find (int x)
{
    if (fa[x] != x) fa[x] = _find(fa[x]);
    return fa[x];
}

struct node
{
 int u, v, w;
 bool operator < (const node & t)
 const
 {
 return w < t.w;
 }
} edge[N] ;

signed main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

cin >> n;
 for (int i = 1; i <= n; ++ i) fa[i] = i;
 for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j <= n; ++ j)
 {
 cin >> a;
 edge[(i - 1) * n + j] = {i, j, a};
 }
 }
 sort (edge + 1, edge + n * n + 1);
 for (int i = 1; i <= n * n; ++ i)
 {
 int a = edge[i].u;
 int b = edge[i].v;
 int c = edge[i].w;
 if (_find(a) != _find(b))
 {
 ans += c;
 fa[_find(a)] = _find(b);
 }
 }
 cout << ans << endl;

return 0;
}

```
### 练习13 [洛谷P2330 [SCOI2005] 繁忙的都市](https://www.luogu.com.cn/problem/P2330)
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int inf = 1061109567;
const int N = 310;
const int M = 8010;

int n, m, a, b, c, fa[N], cnt, ans = - inf;

int _find (int x)
{
    if (fa[x] != x) fa[x] = _find(fa[x]);
    return fa[x];
}

struct node
{
 int u, v, w;
 bool operator < (const node & t)
 const
 {
 return w < t.w;
 }
} edge[M] ;

signed main()
{
 ios :: sync_with_stdio(false);
 cin.tie(0);
 cout.tie(0);
 
 cin >> n >> m;
 for (int i = 1; i <= n; ++ i) fa[i] = i;
 for (int i = 1; i <= m; ++ i)
 {
 cin >> a >> b >> c;
 edge[i] = {a, b, c};
 }
 sort (edge + 1, edge + m + 1);
 for (int i = 1; i <= m; ++ i)
 {
 int a = edge[i].u;
 int b = edge[i].v;
 int c = edge[i].w;
 if (_find(a) != _find(b))
 {
 ++ cnt;
 ans = max(c, ans);
 fa[_find(a)] = _find(b);
 }
 }
 cout << cnt << ' ' << ans << endl;

return 0;
}

```

### 练习14 [洛谷P3831 [SHOI2012] 回家的路](https://www.luogu.com.cn/problem/P3831)
还是蓝题。。。 
分层图：
1. 第一层放横向边
2. 第二层放纵向变
3. 
```cpp
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using P = pair<int, int>;

const int inf = 1061109567;
const int N = 2e5 + 10;

int n, m, dist[N];
bool st[N];
vector col[N];
vector row[N];
vector g[2 * N];
P S, T;

void dijkstra()
{
 priority_queue<P, vector, greater> heap;
 memset (dist, 0x3f, sizeof(dist));

heap.push({0, m + 1});
    dist[m + 1] = 0;
    heap.push({0, 2 * m + 3});
    dist[2 * m + 3] = 0;

while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();

if (st[t.second]) continue;
        st[t.second] = true;

for (auto p : g[t.second])
        {
            int j = p.first;
            if (dist[j] > dist[t.second] + p.second)
            {
                dist[j] = dist[t.second] + p.second;
                heap.push({dist[j], j});
            }
        }
    }

return;
}

signed main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

cin >> n >> m;

for (int i = 1; i <= m; ++ i)
 {
 int u, v;
 cin >> u >> v;
 col[v].push_back({u, i});
 row[u].push_back({v, i});
 g[i].push_back({m + 2 + i, 1});
 g[m + 2 + i].push_back({i, 1});
 }

cin >> S.first >> S.second >> T.first >> T.second;

col[S.second].emplace_back(S.first, m + 1);
    row[S.first].emplace_back(S.second, m + 1);
    g[m + 1].push_back({m + m + 3, 1});
    g[m + m + 3].push_back({m + 1, 1});

col[T.second].emplace_back(T.first, m + 2);
    row[T.first].emplace_back(T.second, m + 2);
    g[m + 2].push_back({m + m + 4, 1});
    g[m + m + 4].push_back({m + 2, 1});

for (int i = 1; i <= n; ++ i)
 {
 sort(row[i].begin(), row[i].end());
 sort(col[i].begin(), col[i].end());
 }

for (int i = 1; i <= n; ++ i)
 {
 for (int j = 1; j < row[i].size(); ++ j)
 {
 P u = row[i][j - 1], v = row[i][j];
 int uy = u.first, vy = v.first;
 int dis = (vy - uy) * 2;

g[u.second].push_back({v.second, dis});
            g[v.second].push_back({u.second, dis});
        }

for (int j = 1; j < col[i].size(); ++ j)
 {
 P u = col[i][j - 1], v = col[i][j];
 int uy = u.first, vy = v.first;
 int dis = (vy - uy) * 2;

g[u.second + m + 2].push_back({v.second + m + 2, dis});
            g[v.second + m + 2].push_back({u.second + m + 2, dis});
        }
    }

dijkstra();

cout << min(dist[m + 2], dist[2 * m + 4]) << endl;

return 0;
}

```

正在渲染内容...