P1462 题解

---

题目大意：

给定一个$n$个点的无向图，求在满足从$1$到$n$的最短路边权和 $\leq b$ 的情况下，所经过的点的最大点权的最小值。

思路：

带有 “最大值最小” 的“双最”字样的最优化题目一般比较难直接求解，这时候我们不妨用二分的思想，将最优化问题转换为判断合法性问题。

二分代码模板：

while(l<=r)
{
  mid=(l+r)>>1;
  if(check(mid)) ans=mid,r=mid-1; //如果解合法，记录答案并缩小左边界
  else l=mid+1;//否则缩小右边界
}
cout<<ans<<endl;

check()函数的设计：

首先，假设我们已经找到了一个解 $val$，那么所有点权 $> val$的点就不能被访问了(因为如果这样做就不满足解)。然后再求出$1$到$n$的最短路 *(SPFAer和Dijkstrer们可以不要争了，这个优先队列BFS就可以做，还比你们都快 233)*，之后判断最短路的权值和是否 $\leq b$ ，如果不满足则说明解不合法 （会被揍死）。

一些小坑点：

• 二分时需要判断 “无论如何也无法到达的情况” ；
• fi≤1000000000,因此直接二分会T飞，要先离散化；
• ci≤1000000000,记得开 long long 不然炸飞；

---

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10005;
typedef long long ll;
int n,m,b;

inline ll read()//快读
{
  ll s=0,w=1;
  char c=getchar();
  while(c<'0' || c>'9'){
    if(c=='-') w=-1;
    c=getchar();
  }
  while (c>='0' && c<='9') {
    s=(s<<3)+(s<<1)+(c^48);
    c=getchar();
  }
  return s*w;
}

/**
 * BFS的记录结构体
 * @param cur 当前点
 * @param c 已经扣掉的血量
 */
struct note{
  ll cur,c;
  note(ll a,ll b):cur(a),c(b) {}
  note() {}
};
//没什么好说的，比较运算符
struct cmp{
  bool operator () (note a,note b)
  {
    return a.c>b.c;
  }
};
//pbds的黑科技堆，详细描述可以看这里：https://blog.xehoth.cc/pb-ds-PriorityQueue/
typedef __gnu_pbds::priority_queue<note,cmp,__gnu_pbds::pairing_heap_tag> heap;

//vector数组存图
struct edge{
  ll to;ll w;
  edge(ll a,ll b):to(a),w(b) {}
  edge() {}
};
vector<edge> e[maxn];
ll v[maxn];//点权数组
/**
 * 增加一条x到y,权值为w的边
 */
inline void addedge(ll x,ll y,ll w)
{
  e[x].push_back(edge(y,w));
}

//BFS部分
bool vis[maxn];
ll bfs(ll val)
{
  memset(vis,0,sizeof(vis));
  heap q;
  q.push(note(1,0));
  vis[1]=true;
  while(!q.empty())
  {
    note cu=q.top();
    q.pop();
    if(cu.cur==n){
      return cu.c;
    }
    ll& st=cu.cur;
    ll& co=cu.c;
    for(int i=0;i<e[st].size();i++)
    {
      ll& to=e[st][i].to;
      if(!vis[to] && v[to]<=val)
      {
        q.push(note(to,co+e[st][i].w));
        vis[to]=true;
      }
    }
  }
  return 0x3f3f3f3f;//如果到不了返回无穷大
}

ll lsv[maxn];//离散数组
int main()
{
  n=read(),m=read(),b=read();
  for(int i=1;i<=n;i++) lsv[i-1]=v[i]=read();
  for(int i=1,x,y,w;i<=m;i++) {
    x=read(),y=read(),w=read();
    if(x!=y) addedge(x,y,w),addedge(y,x,w);
  }
  //离散化
  sort(lsv,lsv+n);
  int sz=unique(lsv,lsv+n)-lsv;
  //二分
  int l=0,r=sz,mid,ans=-1;
  while(l<=r)
  {
    mid=(l+r)>>1;
    if(bfs(lsv[mid])<=b) ans=mid,r=mid-1; 
    else l=mid+1;
  }
  if(ans==-1){//如果答案没被更新过即为“不可到达”
    printf("AFK\n");
    return 0;
  }
  else printf("%lld\n",lsv[ans]);//输出答案
}

总时间复杂度：$O(nlogn * logn) = O(nlog^2 n)$,比几乎所有题解都要快