洛谷 P1462 通往奥格瑞玛的道路

题目连接

分析

注意到很明显的单调性，所以可以使用二分来求解。

接下来我们把城市看成点，公路看成边，把扣血量看成边权，那么从点 $1$ 开始跑一遍最短路，如果点 $1$ 到点 $n$ 的距离（最少扣血量）超过了限制，则不可行，注意不能走到交钱数大于二分限制 $x$ 的点。

注意如果走到了点 $n$，且血量等于 $0$，则也是合法方案。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3 * 1e4 + 5;
int n, m, b, money[N], vis[N], dist[N];

struct node{
  int to, w;
};

vector <node> nbr[N];

bool sqfa(int x){
	if(money[1] > x){
		return false;
	}
	memset(dist, 0x3f, sizeof dist);
	memset(vis, 0, sizeof vis);
  queue <int> q;
  dist[1] = 0, vis[1] = true, q.push(1);
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    vis[cur] = false;
    for(int i = 0; i < nbr[cur].size(); i ++){
      int nxt = nbr[cur][i].to, w = nbr[cur][i].w;
      if(money[nxt] > x){
      	continue;
			}
      if(dist[nxt] > dist[cur] + w){
        dist[nxt] = dist[cur] + w;
        if(!vis[nxt]){
          vis[nxt] = true;
          q.push(nxt);
        }
      }
    }
  }
  return dist[n] < b;
}

signed main(){
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i ++){
  	    cin >> money[i];
	}
	for(int i = 1; i <= m; i ++){
		int a, b, c;
		cin >> a >> b >> c;
		nbr[a].push_back((node){b, c});
		nbr[b].push_back((node){a, c});
	}
	int l = -1, r = 1e9 + 1;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(sqfa(mid)){
			r = mid;
		}else{
			l = mid;
		}
	}
	if(!sqfa(r)){
		cout << "AFK";
	}else{
		cout << r;
	}
}