·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：https://hihocoder.com/problemset/problem/1139
二分索敌值，用BFS遍历，判断能不能在规定步数内走到终点即可。注意不能用DFS（可能是因为路径非最短）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int maxn=10000 + 10;
const int maxm=100000 + 10;
struct Edge {
int u,v,cap,next;
}edge[maxm*2];
int head[maxn];
bool vis[maxn];
int n,m,s,t,ne=0,k;
void insert(int u,int v,int cap) {
edge[ne].v=v;edge[ne].cap=cap;edge[ne].next=head[u];head[u]=ne++;
edge[ne].v=u;edge[ne].cap=cap;edge[ne].next=head[v];head[v]=ne++;
}
int mid;
bool bfs() {
memset(vis, 0, sizeof(vis));
std::queue<int> q;
std::queue<int> d;
vis[s] = 1;
q.push(s);
d.push(0);
while(!q.empty()) {
int u = q.front(), dep = d.front();
q.pop(); d.pop();
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].v;
if (!vis[v] && edge[i].cap <= mid && dep+1 <= k) {
if (v == t) return 1;
vis[v] = 1;
q.push(v);
d.push(dep+1);
}
}
}
return 0;
}
bool check() {
return bfs();
}
int main() {
int u, v, cap;
int maxw = 0;
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &k, &t);
s = 1;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &cap);
maxw = std::max(maxw, cap);
insert(u, v, cap);
}
if (t == 1) {
printf("0");
return 0;
}
int l = 1, r = maxw;
while (l < r) {
mid = (l+r) >> 1;
if (check()) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}