二分加最短路。
因为原题中要求给定一个值n和一个次数m，使这个值尽量小的同时存在一条1到n的路径上权值大于该值的边的个数小于次数m。
此时我们发现该值和次数满足单调性，即该值越小个数越多。
因此可以用二分，再考虑如何check
可以将路上的权值是否大于n这一条件做布尔边权值，这样跑出来的最短路即为路径的最小次数。
注意是双向图。
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
struct edge {
int t, l, nex;
int l2;
}e[100010], ne[100100];
int lin[100100], cnt, n, m, k, dis[101000], vis[1001000];
inline void add(int a, int b, int c)
{
e[++cnt].t = b;
e[cnt].l = c;
e[cnt].nex = lin[a];
lin[a] = cnt;
}
bool check (int mid)
{
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= cnt; i++)
{
if (e[i].l > mid)
e[i].l2 = 1;
else
e[i].l2 = 0;
// printf("%d %d %d\n", mid, e[i].l, e[i].l2);
}
queue <int> q;
q.push(1);
for (int i = 1; i <= n; i++)
dis[i] = 214743647;
dis[1] = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
vis[cur] = 0;
for (int i = lin[cur]; i; i = e[i].nex)
{
if (dis[cur] + e[i].l2 < dis[e[i].t])
{
dis[e[i].t] = dis[cur] + e[i].l2;
if (!vis[e[i].t])
q.push(e[i].t), vis[e[i].t] = 1;
}
}
}
// printf("%d %d\n", mid, dis[n]);
if (dis[n] <= k) return 1;
else return 0;
}
int main()
{
int minn = 2147483647, maxn = 0;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
minn = min(minn, c);
maxn = max(maxn, c);
}
int l = 0, r = maxn + 1000, mid, ans = -1;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid))
r = mid - 1, ans = mid;
else
l = mid + 1;
}
printf("%d", ans);
return 0;
}洛谷 P4377 [USACO18OPEN]Talent Show
原文：https://www.cnblogs.com/liuwenyao/p/11221558.html