《信息学奥赛一本通 提高篇》题解 架设电话线

这道题没有那么难的吧

咳咳我们开始正题

题意简述一下，就是在加权无向图上求出一条从号结点到号结点的路径，使路径上第大的边权尽量小

恩，作为一名OIER，我们先看一下题解数据范围

好的不大，我们可以跑好多次最短路(逃

由于题目求最值，那就二分答案喽

我们转化问题：二分，每次判断是否能使到的路径上第大的边权小于。那么只需要把升级价格大于的边权值赋为1，其余权值赋为0，跑最短路得到与进行比较，若小于等于，说明该答案可行，缩小继续二分，否则缩小。

至于跑最短路，各种神仙算法都可以，反正我用的。

上代码（或许有的人只看这个）：

宏定义不要在意，个人习惯哈哈

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define lowbit(x) (x)&(-x)
#define oo (1e18)
#define soo (1e9)
#define INF 2147483647
#define Bigprime 212370440130137957int
#define ll long long
#define LL unsigned long long
#define lll __int128
#define hash Hash
#define gc getchar()
#define pc(x) putchar(x)
#define ls(x) x<<1
#define rs(x) x<<1|1
#define hh puts("")
#define mp make_pair
#define fi first
#define se second
using namespace std;
int head[1005],dis[1005],n,p,k,cnt,tot,s[100005];
bool vis[1005];
struct Edge{
    int u,v,s,nx;
}e[100005];
inline ll read(){
    ll ret=0,ff=1;char c=gc;
    while(!isdigit(c)){if(c=='-') ff=-ff;c=gc;}
    while(isdigit(c)){ret=(ret<<3)+(ret<<1)+c-'0';c=gc;}
    return ret*ff;
}
void add(int x,int y){
    e[++cnt].u=x;
    e[cnt].v=y;
    e[cnt].nx=head[x];
    head[x]=cnt;
}
void spfa(){
    for(int i=1;i<=n;i++) dis[i]=soo,vis[i]=0;
    vis[1]=1,dis[1]=0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nx){
            int y=e[i].v,z=e[i].s;
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int main(){    
    n=read(),p=read(),k=read();
    for(int i=1;i<=p;i++){
        int x=read(),y=read(),z=read();
        s[++tot]=z;
        s[++tot]=z;
        add(x,y);
        add(y,x);
    }
    int ans=-1;
    int l=0,r=1000000;
    while(l<=r){
        int mid=(l+r)>>1;
        for(int i=1;i<=cnt;i++){
            if(s[i]<=mid) e[i].s=0;
            else e[i].s=1;
        }
        spfa();
        if(dis[n]<=k){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}