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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
using namespace std;
struct Node {
vector<int> neighbors;
vector<int> edges;
};
bitset<10001> set;
bool bfs(Node* graph, int s, int t, int k, int w) {
queue<int> visited;
queue<int> level;
visited.push(s);
level.push(0);
while (!visited.empty()) {
int root = visited.front();
visited.pop();
int l = level.front();
level.pop();
if (l > k)
return false;
if (root == t)
return true;
for (int i = 0; i < graph[root].neighbors.size(); i++) {
if (!set[graph[root].neighbors[i]]) {
if (graph[root].edges[i] <= w) {
set[graph[root].neighbors[i]] = 1;
visited.push(graph[root].neighbors[i]);
level.push(l + 1);
}
}
}
}
return false;
}
bool sat(Node* graph, int t, int k, int w) {
set.reset();
return bfs(graph, 1, t, k, w);
}
int calMin(Node* graph, int t, int k, int left, int right) {
if (left + 1 == right)
return right;
int mid = (right - left) / 2 + left;
if (sat(graph, t, k, mid))
return calMin(graph, t, k, left, mid);
else
return calMin(graph, t, k, mid, right);
}
int main() {
int N = 0, M = 0, K = 0, T = 0;
cin >> N >> M >> K >> T;
Node* graph = new Node[N + 1];
int minW = 1000001;
int maxW = 0;
for (int i = 0; i < M; i++) {
int a = 0, b = 0, w = 0;
cin >> a >> b >> w;
graph[a].neighbors.push_back(b);
graph[a].edges.push_back(w);
graph[b].neighbors.push_back(a);
graph[b].edges.push_back(w);
maxW = max(maxW, w);
minW = min(minW, w);
}
cout << calMin(graph, T, K, minW, maxW) << endl;
return 0;
}
|
