Luogu P1951 收费站_NOI导刊2009提高（2）

二分答案+堆优Dijkstra

• 这个题有些巧妙。
• 首先，因为要在油量耗完之前跑到终点，所以我们可以用最短路。只要从\(s\)出发到\(t\)，它的最短距离大于油量，我们就可以断定它一定走不通，直接输出\(-1\)。
• 然后因为要求最大值最小，所以考虑二分答案。用一个数组来储存点的值从大到小的排序，然后边界范围设置 : \(L\)为\(s\)和\(t\)的中较大的拿一个的排名,\(R\)为n。为什么\(L\)要这样设置呢？因为\(s\)和\(t\)是必经的点，所以它们一定要选，所以最小值只能设为它们之间较大的一个。
• 但是在存边的时候要注意，没有必要判重！！！因为两条路，他们连接的点可能一样，但是他们的距离不同，所以判重还会导致花费更多没必要的时间。我就是被说明给坑了。。。
• 上代码，有不清楚的代码里面尽量写明。

#include<bits/stdc++.h>
#define clean(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x) //快读
{
    int f=1;char k=getchar();x=0;
    for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
    for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
    x*=f;
}
const int MAXN = 1e4+5,MAXM= 5e4+5;
int n,m,s,t,mx,u,v,d,num_edge,head[MAXN],val[MAXN],p[MAXN],dis[MAXN],l,r; //p数组用来存每个点的权值排序后的顺序
struct Edge{
    int next,to,dis;
    Edge(){}
    Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXM<<1]; //加边，无向边开两倍
il add_edge(int u,int v,int dis){
    edge[++num_edge]=Edge(head[u],v,dis);head[u]=num_edge;
    edge[++num_edge]=Edge(head[v],u,dis);head[v]=num_edge;
} //用结构体的生成函数写，方便又简洁
struct Node{
    int dis,pos;
    Node(){}
    Node(int dis,int pos):dis(dis),pos(pos){}
    bool operator <(const Node &t) const{
        return dis>t.dis;
    }
}; //用来跑Dijkstra，堆优要用
bool tr[MAXN]; //判断是否用这个点松弛过
il dijkstra(int lim){ //lim用来限制通过的点的最大权值
    priority_queue<Node> q;q.push(Node(0,s));
    clean(tr,0);clean(dis,0x3f);dis[s]=0; //初始化
    while(!q.empty()){
        Node tmp=q.top();q.pop();
        ri pos=tmp.pos;
        if(tr[pos]||val[pos]>lim) continue;
        tr[pos]=true;
        for(ri i=head[pos];i;i=edge[i].next){
            if(dis[edge[i].to]>dis[pos]+edge[i].dis){
                dis[edge[i].to]=dis[pos]+edge[i].dis;
                if(!tr[edge[i].to]) q.push(Node(dis[edge[i].to],edge[i].to));
            }
        }
    }
} //这个基本是堆优Dijkstra的模板，当然，在写法上可能有不同，不会的小伙伴可以去看一下 P4779 【模板】单源最短路径（标准版）
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n),read(m),read(s),read(t),read(mx); //读入
    for(ri i=1;i<=n;i++) read(val[i]),p[i]=val[i]; 
    for(ri i=1;i<=m;i++){
        read(u),read(v),read(d);
        if(d>mx) continue;
        add_edge(u,v,d);
    } //加边
    sort(p+1,p+1+n); //给每个点的权值排序
   dijkstra(p[n]); //先用最大的跑一遍，如果走不通，说明无解
    if(dis[t]>mx){
        printf("-1");
        return 0;
    }
    for(ri i=1;i<=n;i++) if(p[i]==max(val[s],val[t])) {l=i;break;} //确定l的取值
    r=n;
    while(l<r){ //二分答案
        dijkstra(p[mid]);
        if(dis[t]>mx) l=mid+1;
        else r=mid;
    }
    printf("%d",p[l]); //输出
    return 0;
}

• 愉快收工！！[]~(￣▽￣)~*

  顺便安利一下自己的博客 虽然还几乎啥都没有

Luogu P1951 收费站_NOI导刊2009提高（2）

原文：https://www.cnblogs.com/TheShadow/p/10659917.html