Time Lapse :1hour 18min 50sec
1800.cpp
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
| #include <iostream>
#include <algorithm>
#include <list>
#include <queue>
using namespace std;
int n, p, k;
list<pair<int,int>> line[1001];
bool binarySearch(int cost) {
priority_queue<pair<int, int>> pq;
pq.push({0, 1});
int g[1001];
g[1] = 0;
for(int i = 2; i<= n; i++)
g[i] = 987654321;
while(!pq.empty()) {
int pos = pq.top().second;
int c = -pq.top().first;
pq.pop();
if(g[pos] < c) continue;
for(pair<int,int> p : line[pos]) {
int nc = c + (p.second > cost);
if(nc < g[p.first]) {
g[p.first] = nc;
pq.push({-nc, p.first});
}
}
}
return g[n] <= k;
}
int main() {
scanf("%d %d %d", &n, &p, &k);
for(int i = 0; i < p; i++) {
int a, b, c;
scanf("%d %d %d",&a,&b,&c);
line[a].push_back(make_pair(b,c));
line[b].push_back(make_pair(a,c));
}
int ans = -1;
int l = 0, r = 1000001, m;
while(l < r) {
m = (l + r) / 2;
if(binarySearch(m)) {
ans = m;
r = m;
} else
l = m + 1;
}
printf("%d",ans);
}
|
