[Usaco2007 Jan]Telephone Lines架设电话线（最短路，二分）

2024-03-17 15:31:10

[Usaco2007 Jan]Telephone Lines架设电话线

Description

FarmerJohn打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。

第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i(1<=L_i<=1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。经过谈判，电信公司最终同意免费为FJ连结K(0<=K<N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。请你计算一下，FJ最少需要在电话线上花多少钱。

Input

第1行: 3个用空格隔开的整数：N，P，以及K
第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i

Output

第1行: 输出1个整数，为FJ在这项工程上的最小支出。

如果任务不可能完成，输出-1

Sample Input

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

输入说明:

一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信公司可以免费为FJ连结一对电话线杆。

Sample Output

4

输出说明:

FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，他所需要购买的电话线的最大长度为4。

一道屯了很久的题目，感觉自己下次再碰到同一类型题目还是不容易想到二分，不过貌似二分和图论很配哦？？？

对于二分答案，我们要从答案的单调性入手，这道题，显然花费更多的钱，会使得电信公司免费的线路数量更少，答案具备单调性，所以我们可以二分花费，将大于花费的电线权值视为1，其余的视为0，跑一遍最短路，判断到\(n\)经过的最少的免花费电线。

注意：-1的情况为无法到达n

#include<bits/stdc++.h>

using namespace std;

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

const int N=1010;

int n,p,k,cnt,l,r,mid,x,y,z,flag;

int head[N],dis[N],vis[N];

queue<int> q;

struct node{

    int v,to,next;

}edge[20*N];

void add(int x,int y,int z)

{

    cnt++;edge[cnt].to=y;edge[cnt].v=z;edge[cnt].next=head[x];head[x]=cnt;

}

int d(int v,int k)

{

    if(v>k) return 1;return 0;

}

bool check(int w)

{

    memset(dis,0x3f,sizeof(dis));

    q.push(1);vis[1]=1;dis[1]=0;

    while(!q.empty())

    {

        int u=q.front();vis[u]=0;q.pop();

        for(int i=head[u];i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(dis[v]>dis[u]+d(edge[i].v,w))

            {

                dis[v]=dis[u]+d(edge[i].v,w);

                if(!vis[v]) vis[v]=1,q.push(v);

            }

        }

    }

    if(dis[n]==dis[0]) flag=1;

    if(dis[n]>k) return false;return true;

}

int main()

{

    n=read();p=read();k=read();

    for(int i=1;i<=p;i++)

    {

        x=read();y=read();z=read();

        add(x,y,z);add(y,x,z);r=max(r,z);

    }

    while(l<r)

    {

        mid=(l+r)/2;

        if(check(mid)) r=mid;

        else l=mid+1;

        if(flag){cout<<-1;return 0;}

    }

    cout<<l<<endl;

    return 0;

}

码农公寓