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

2024-01-02 18:25:20

题目连接

分析

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

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

注意如果走到了点 n n n,且血量等于 0 0 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;
	}
} 

文章来源:https://blog.csdn.net/zc2000911/article/details/135344315
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。