poj3662 Telephone Lines

思路：
二分+最短路。最短路也可以用来计算从a到达b所需的边权不超过x的边的数量。
实现：
 1 #include <cstdio>
 2 #include <cmath>
 3 #include <queue>
 4 #include <cstring>
 5 using namespace std;
 6 const int INF = 0x3f3f3f3f;
 7 const int MAXN = 1005;
 8 int G[MAXN][MAXN], d[MAXN];
 9 bool in[MAXN];
10 int n, p, k;
11 int spfa(int s, int t, int x)
12 {
13     memset(in, false, sizeof in);
14     memset(d, 0x3f, sizeof d);
15     queue<int> q;
16     d[s] = 0;
17     q.push(s);
18     in[s] = true;
19     while (!q.empty())
20     {
21         int tmp = q.front(); q.pop();
22         in[tmp] = false;
23         for (int i = 1; i <= n; i++)
24         {
25             int w = INF; 
26             if (G[tmp][i] != INF) w = G[tmp][i] > x ? 1 : 0;  
27             if (d[tmp] + w < d[i])
28             {
29                 d[i] = d[tmp] + w;
30                 if (!in[i]) { in[i] = true; q.push(i); }
31             }
32         }
33     }
34     return d[t];
35 }
36 bool check(int x)
37 {
38     int cnt = spfa(1, n, x);
39     return cnt <= k;
40 }
41 int main()
42 {
43     scanf("%d %d %d", &n, &p, &k);
44     int a, b, w, maxw = -INF;
45     memset(G, 0x3f, sizeof G);
46     for (int i = 0; i < p; i++) 
47     {    
48         scanf("%d %d %d", &a, &b, &w);
49         G[a][b] = G[b][a] = w;
50         maxw = max(maxw, w);
51     }
52     int l = 0, r = maxw, ans = INF;
53     while (l <= r)
54     {
55         int m = l + r >> 1;
56         if (check(m)) { ans = m; r = m - 1; }
57         else l = m + 1;
58     }
59     if (ans == INF) puts("-1");
60     else printf("%d
", ans);
61     return 0;
62 }