LOJ10074架设电话线

2024-10-10 09:49:16

USACO 2008 Jan. Silver

在郊区有 N 座通信基站，P 条双向电缆，第 i 条电缆连接基站 Ai 和 Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第i 条电缆需要花费Li。

电话公司正在举行优惠活动。农场主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。

一句话题意 \ \ 在加权无向图上求出一条从 1 号结点到 N 号结点的路径，使路径上第K+1 大的边权尽量小。

输入格式

第一行三个整数 N,P,K.

接下来 P 行，每行三个整数 Ai,Bi,Li.

输出格式

若不存在从 1 到 N 的路径，输出 -1。否则输出所需最小费用。

样例

样例输入

样例输出

数据范围与提示

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

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

二分付费边的长度。

那么所有小于等于该长度的边设为0，大于它的边的长度设为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 }

最新文章

热门文章