【洛谷P1948】[USACO08JAN]电话线

电话线

题目链接：https://www.luogu.org/problemnew/show/P1948

二分答案+最短路

我们要求一条1~n的路径，使其中的第k+1大的数最小。

二分第k+1大的数的大小h，比h小的边可以看为0，因为它们不会让第k+1大的数更大；比h大的边边权设为1，最后求出的1~n的最短路，就是在第k+1大的数小于等于h时需要让电信公司承担的电话线数，因为在第k+1大的数的大小限制为h的情况下，任何比h大的数都不可以自己承担。若dis[n]>k返回false，否则返回true。

不知为啥跑的贼慢。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 const int INF = 2147483647 ;
 7 struct Edge{　　　　　　　　　　//邻接表
 8     int to;
 9     int w;
10     int next;
11 } edge[100010];
12 int sum,n,p,k,head[10010];
13 void add(int x,int y,int w)
14 {
15     edge[++sum].next=head[x];
16     edge[sum].to=y;
17     edge[sum].w=w;
18     head[x]=sum;
19 }
20 int dis[10010];
21 struct cmp{
22     bool operator () (int a,int b)
23     {
24         return dis[a]>dis[b];
25     }
26 };
27 priority_queue < int , vector<int> , cmp > q;
28 void clear(priority_queue< int , vector<int> , cmp > &qq)　　//清空队列
29 {
30     priority_queue < int , vector<int> , cmp > empty;
31     swap(qq,empty);
32 }
33 bool dijkstra(int _std)　　　　　　//堆优化dijkstra
34 {
35     for(int i=1;i<=n;i++)
36      dis[i]=INF;
37     bool v[10010]={0};
38     clear(q);
39     q.push(1);
40     dis[1]=0;
41     while(!q.empty())
42     {
43         int k=q.top();
44         q.pop();
45         if(v[k]) continue;
46         v[k]=1;
47         for(int i=head[k];i;i=edge[i].next)
48         {
49             int j=edge[i].to;
50             if(!v[j]&&dis[j]>int(edge[i].w>_std)+dis[k])
51              dis[j]=int(edge[i].w>_std)+dis[k];
52             q.push(j);
53         }
54         
55     }
56     return dis[n]<=k;
57 }
58 int main()
59 {
60     scanf("%d%d%d",&n,&p,&k);
61     int x,y,w;
62     for(int i=1;i<=p;i++)
63     {
64         scanf("%d%d%d",&x,&y,&w);
65         add(x,y,w);
66         add(y,x,w);
67     }
68     int l=0,r=1000000;
69     while(l<r)　　　　//二分
70     {
71         int mid=(l+r)>>1;
72         if(dijkstra(mid)) r=mid;
73         else l=mid+1;
74     }
75     if(l==1000000) l=-1;
76     printf("%d
",l);
77     return 0;
78 }