USACO 2008 Jan. Silver

在郊區(qū)有?N?座通信基站，P?條雙向電纜，第?i?條電纜連接基站?Ai??和?Bi?。特別地，1?號基站是通信公司的總站，N?號基站位于一座農(nóng)場中?，F(xiàn)在，農(nóng)場主希望對通信線路進行升級，其中升級第i?條電纜需要花費Li?。

電話公司正在舉行優(yōu)惠活動。農(nóng)場主可以指定一條從?1?號基站到?N?號基站的路徑，并指定路徑上不超過?K?條電纜，由電話公司免費提供升級服務(wù)。農(nóng)場主只需要支付在該路徑上剩余的電纜中，升級價格最貴的那條電纜的花費即可。求至少用多少錢能完成升級。

一句話題意?\ \???在加權(quán)無向圖上求出一條從?1?號結(jié)點到?N?號結(jié)點的路徑，使路徑上第K+1?大的邊權(quán)盡量小。

輸入格式

第一行三個整數(shù)?N,P,K.

接下來?P?行，每行三個整數(shù)?Ai?,Bi?,Li?.

輸出格式

若不存在從?1?到?N?的路徑，輸出?-1。否則輸出所需最小費用。

樣例

樣例輸入

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

樣例輸出

4

數(shù)據(jù)范圍與提示

0≤K<N≤1000,1≤P≤2000

——————————————————————————————

二分付費邊的長度。

那么所有小于等于該長度的邊設(shè)為0，大于它的邊的長度設(shè)為1，那么如果從點1到點n的最短距離小于等于k，說明可以可以建起，否則不可以。

注意判斷-1。

——————————————————————————————

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1010;
 4 const int maxm=2010;
 5 int n,m,k;
 6 struct edge
 7 {
 8     int u,v,w,ww,nxt;
 9 }e[maxm<<1];
10 int head[maxn],js;
11 void addage(int u,int v,int w)
12 {
13     e[++js].u=u;e[js].v=v;e[js].w=w;
14     e[js].nxt=head[u];head[u]=js;
15 }
16 int l,r,ans;
17 struct node
18 {
19     int dis,p;
20     bool operator < (node b)const 
21     {
22         return dis>b.dis;
23     }
24 };
25 
26 bool vis[maxn];
27 int dis[maxn];
28 bool pd(int x)
29 {
30     for(int i=1;i<=m+m;++i)e[i].ww=e[i].w<=x?0:1;
31     memset(dis,0x3f,sizeof dis);
32     memset(vis,0,sizeof vis);
33     priority_queue< node > q;
34     dis[1]=0;
35     q.push((node){0,1});
36     while(!q.empty())
37     {
38         node t=q.top();
39         q.pop();
40         int d=t.dis,p=t.p;
41         if(vis[p])continue;
42         vis[p]=1;
43         for(int i=head[p];i;i=e[i].nxt)
44         {
45             int v=e[i].v;
46             if(dis[v]>dis[p]+e[i].ww)
47             {
48                 dis[v]=dis[p]+e[i].ww;
49                 q.push((node){dis[v],v});
50             }
51         }
52     }
53     if(dis[n]==0x3f3f3f3f)
54     {
55         puts("-1");
56         exit(0);
57     }
58     return dis[n]<=k;
59 }    
60 int main()
61 {
62     scanf("%d%d%d",&n,&m,&k);
63     for(int u,v,w,i=0;i<m;++i)
64     {
65         scanf("%d%d%d",&u,&v,&w);
66         addage(u,v,w);addage(v,u,w);
67         r=max(r,w);
68     }
69     while(l<=r)
70     {
71         int mid=(l+r)>>1;
72         if(pd(mid))ans=mid,r=mid-1;
73         else l=mid+1;
74     }
75     cout<<ans;
76     return 0;
77 }

View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/gryzy/p/10533795.html

總結(jié)

以上是生活随笔為你收集整理的LOJ10074架设电话线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。