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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
struct Edge
{
int v, w;
Edge *next;
} g[10000*2];
int n, m, k, LinkSize, road[10000][3];
Edge* header[1000];
void add_edge(const int x, const int y, const int w)
{
Edge* node = g+(LinkSize++);
node->v = y;
node->w = w;
node->next = header[x];
header[x] = node;
}
int SPFA(const int source)
{
std::queue<int> q;
std::bitset<1000> s;
std::vector<int> dist(n, 0x3FFFFFFF);
q.push(source);
s.set(source, true);
dist[source] = 0;
while (!q.empty())
{
const int u = q.front();
for (Edge* e = header[u]; e; e = e->next)
if (dist[e->v] > dist[u] + e->w)
{
dist[e->v] = dist[u] + e->w;
if (!s.test(e->v))
{
s.set(e->v, true);
q.push(e->v);
}
}
s.set(u, false);
q.pop();
}
return dist[n-1];
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &road[i][0], &road[i][1], &road[i][2]);
--road[i][0], --road[i][1];
}
int lef(-1), rig(1000001);
while (rig-lef > 1)
{
memset(header, 0, sizeof(header));
LinkSize = 0;
const int mid((lef+rig)>>1);
for (int i = 0; i < m; ++i)
{
const int d = road[i][2] > mid ? 1 : 0;
add_edge(road[i][0], road[i][1], d);
add_edge(road[i][1], road[i][0], d);
}
if (SPFA(0) <= k)
rig = mid;
else
lef = mid;
}
printf("%d", rig == 1000001 ? -1 : rig);
}
|
