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

「爱情、让人受尽委屈。」 2023-07-18 04:50 9阅读 0赞

## 题目背景 ##

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量

有一天他醒来后发现自己居然到了联盟的主城暴风城

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛

## 题目描述 ##

在艾泽拉斯，有n个城市。编号为1,2,3,...,n。

城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

## 输入格式 ##

第一行3个正整数，n，m，b。分别表示有n个城市，m条公路，歪嘴哦的血量为b。

接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。

再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，会损失ci的血量。

## 输出格式 ##

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出AFK。

## 输入输出样例 ##

**输入 \#1**

4 4 8
    8
    5
    6
    10
    2 1 2
    2 4 1
    1 3 4
    3 4 3

**输出 \#1**

## 说明/提示 ##

对于60%的数据，满足n≤200，m≤10000，b≤200

对于100%的数据，满足n≤10000，m≤50000，b≤1000000000

对于100%的数据，满足ci≤1000000000，fi≤1000000000，可能有两条边连接着相同的城市。

**题目解析：能决定歪嘴哦是否可以到达奥格瑞玛的因素只有一个，就是血量，金钱并不会限制他的到达。也就说歪嘴哦是个土豪，无论收费站收取多少钱，他都能支付的起，导致他到达不了奥格瑞玛的唯一原因就是血条没了。但是歪嘴哦不是个败家子，他还是想知道，在他能顺利到达奥格瑞玛的前提下，路径上收费站收取金币的最大值（这个最大值是单个收费站收取金币的最大值，而不是整条路径的最大值）是多少。**

原文：他所经过的所有城市中最多的一次收取的费用的最小值是多少。

解读一下这句话：在血量满足的情况下，从起点到终点的路径可能有多条，假设从**暴风城**到**奥格瑞玛**的

第一条路径上，单个收费站收取的金币最大值为X1。

第二条路径上，单个收费站收取的金币最大值为X2。

第三条路径上，单个收费站收取的金币最大值为X3。

第N条路径上，单个收费站收取的金币最大值为Xn。

我要求的答案就是min(x1,x2,x3,...,xn);

也就是路径上最多的一次收取费用，其中的最小值。

这就是一种经典题型：最大值中的最小值。大家可以直接在网上搜二分法最大值最小值，有很多题。

思路解析：二分法+最短路（Dijkstra或者SPFA都可以）。

1. 明确二分法是对谁进行的二分，一般这种题目是对最大值进行的二分，这里的最大值也就是**单条路径上收取的最大一次金币**，我们首先对所有收费站**按照收取的金币数量**进行从小到大排序（想用二分，必须排序）。假设数组是money\[MAXN\]，我们先选择中间那个值money\[mid\]（mid = (1 + n)/2），我们试一下**把money\[mid\]对应的金币作为某条路径上单个收费站收取金币的上限**，看看在这种情况下，从起点到终点能不能走通，如果可以走通，那就向左二分（也就是**缩小**单个收费站收取金币的**上限**），如果走不通，那就向右二分（也就是**扩大**单个收费站收取金币的**上限**）。

2. 至于判断能否走通的方法，就是用最短路，把血量作为标尺，找出从起点到源点的最小耗血量（在收费站收取金币有上限的情况下），如果最小耗血量低于**歪嘴哦**的满血量，那就说明可以走通，如果最小耗血量都大于**歪嘴哦**的满血量，那肯定走不通了。

蒟蒻表达能力有限，如果还有疑问，在评论区说明一下吧。

#include<bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    using namespace std;
    const int MAXN = 10002; 
    const long long INF = 1000000010;
    
    struct Node{
    	int v;
    	long long w;
    	Node(int v,int w){
    		this->v = v;
    		this->w = w;
    	}
    };
    vector<Node> adj[MAXN];  //邻接表 
    long long dis[MAXN];     //耗血量 
    long long money[MAXN];   //从键盘输入的每个收费站的过路费 
    long long point[MAXN];   //根据过路费从小到大排序后的收费站过路费 
    queue<int> que;    
    bool vis[MAXN];    //vis[u]=true; 表示u节点在队列中 
    int n,m;  //城市个数、城市个数
    long long b; //血量 
    
    /*
    ** 第一标尺是耗血量 
    */
    bool SPFA(int top){  //top:单个收费站收取过路费的上限 
    	fill(dis,dis+n+1,INF); 
    	dis[1] = 0; 
    	que.push(1);
    	vis[1] = true;
    	while(!que.empty()){
    		int u = que.front();
    		que.pop();
    		vis[u] = false;
    		for(int i=0;i<adj[u].size();i++){
    			int v = adj[u][i].v;
    			int w = adj[u][i].w;  //从u--->v耗费的血量		
    			if(dis[v] > dis[u] + w && money[v]<=top){ //是不是可以松弛并且不超过收费上限 
    				dis[v] = dis[u] + w;
    				if(!vis[v]){
    					que.push(v);
    					vis[v] = true;	
    				}
    			}
    		}
    	}
    	return dis[n]<b?true:false;
    }
    
    int binarySearch(int left,int right){
    	int ans = 0; 
    	while(left <= right){
    		int mid = (left+right)/2;
    		if(SPFA(point[mid])){  //如果在point[mid]作为上限的情况下，从源点到终点有路可达 
    			ans = point[mid];
    			right = mid - 1;   //缩小上限 
    		}else{ 
    			left = mid + 1;    //如果不可达：扩大上限 
    		}
    	}
    	return ans;
    } 
    
    int main(){
    	int u,v;
    	long long w;
    	cin>>n>>m>>b;
    	for(int i=1;i<=n;i++){
    		cin>>money[i];
    		point[i] = money[i];  //用来排序 
    	}
    	while(m--){
    		cin>>u>>v>>w;
    		adj[u].push_back(Node(v,w));
    		adj[v].push_back(Node(u,w));
    	}
    	if(!SPFA(INF)){  //在过路费没有上限的情况下，依然没有可达路径。 
    		cout<<"AFK"<<endl;  //说明起点到终点根本不连通。 
    	}else{
    		sort(point+1,point+n+1);  //左闭右开，默认升序 
    		cout<<binarySearch(1,n)<<endl;
    	}
    	return 0;
    }