题解 | TelephoneLines-牛客假日团队赛8F题

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.
There are forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of pairs of poles can be connected by a cable; the rest are too far apart.
The i-th cable can connect the two distinct poles Ai and Bi, with length units if used. The input data set never names any pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.
As it turns out, the phone company is willing to provide Farmer John with lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.
Determine the minimum amount that Farmer John must pay.

第一个想到的当然是枚举~(≧▽≦)/~啦啦啦

然后就 TLETLE 了QAQ

这道题目显然要用二分去做，那么，二分什么呢？当然是二分答案，本题有一个很和谐的友好的字眼：答案是最长的长度。

至于思路如下：首先二分答案，将所有线中大于答案的标记为 11 （需要使用一次免费机会）,不大于答案的标记为0（不需要使用免费机会）,有人说，这题不能用Dijkstra？当然不行，为什么呢？因为迪杰斯特拉算法效率低下他无法对0边权进行处理，极有可能死循环，而SPFA的原理是：更新后不低于当前长度就不进队列，可以有效的处理0的问题。

代码如下

#include<bits/stdc++.h>//万能头
using namespace std;
inline int read() {//快读
    int X=0,w=0;
    char ch=0;
    while(!isdigit(ch)) {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline double dbread() {//小数快读
    double X=0,Y=1.0;
    int w=0;
    char ch=0;
    while(!isdigit(ch)) {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
    ch=getchar();
    while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x) {//快些
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

至此为止，上面都是我的模板AwA

struct node {//程序核心
    int to,next,val;
} e[20005];//前向星
int tot=0,head[1005],dis[1005],n,k,p,ans=-1;
bool vis[1005];
queue<int> q;//SPFA队列
void add(int u,int v,int w) {//建边(前向星)
    e[++tot]=(node) {
        v,head[u],w
    };
    head[u]=tot;
}
bool spfa(int x) {//SPFA(judge函数)
    memset(dis,42,sizeof(dis));//初始化,因为有多次judge
    memset(vis,0,sizeof(vis));//初始化,因为有多次judge
    dis[1]=0;
    q.push(1);
    vis[1]=true;
    int s;
    while(!q.empty()) {//SPFA（STL队列实现）
        int now=q.front();
        q.pop();
        for(int i=head[now]; i; i=e[i].next) {
            if(e[i].val>x)s=dis[now]+1;//如果大于当前二分出来的答案（如上所述）
            else s=dis[now];
            if(s<dis[e[i].to]) {
                dis[e[i].to]=s;
                if(!vis[e[i].to])q.push(e[i].to),vis[e[i].to]=true;
            }
        }
        vis[now]=0;
    }
    if(dis[n]<=k)return 1;//如果需要免费的边在范围之内，说明这种答案是可行的,寻找更小的答案
    return 0;
}
int main() {
    n=read();//读入
    p=read();//读入
    k=read();//还是读入
    for(int i=1; i<=p; i++) {//建边
        int u,v,w;
        u=read();
        v=read();
        w=read();
        add(u,v,w);//因为是无向图，所以要建来去两边
        add(v,u,w);
    }
    int l=0,r=1000000;
    //二分,我这里直接从最大距离开始查找，你们也可以从输入的数据中找最大值（可能会比我这个快一点）
    while(l<=r) {//二分
        int mid=(l+r)>>1;
        if(spfa(mid)) {
            ans=mid;//保存下当前答案，就可以放心的去找更小的了
            r=mid-1;
        } else l=mid+1;
    }
    write(ans);//输出
    return 0;//这可是个好习惯
}

关于二分，有很多写法，我个人喜欢这种写法，找到答案之后保存下来，有一些写法是输出R或L的，这个就要看个人喜好了

来源：蒟蒻小水楼