一道不简单的题：堆优化Dijkstra +二分答案
这题确实有点难（说白了我以前就是在用"水题浪费生命！"——这话应该是Du老师说的）
上题目：洛谷 P1462 提高+/省选-难度（基础知识的活用）
题意：
这题说的就是，如果血量不足以消耗到终点，那么就GG，输出AFK（一开始我输出AKF，气哭……）然后如果能够到达终点，问在可以到达终点的情况下，那条方案路径的经过的最大节点是所有方案经过的最大节点中最小的？？
算法分析：
为什么想到二分答案？
一看到这种最大节点最小，最小节点最大，这种就是二分答案的典序特征！为什么呢？？
因为二分搜索里有一种情况，就是要寻找序列中某个数最后（或最先）一次出现的位置，假设位置也有大小区别，那么最后一次出现的那个数和最先出现的数虽然是同一个数，但是在位置上是有大小区别的！那么我们这个问题也是如此，经过最大节点最小的路径方案虽然和经过最大节点非最小的方案都是可行方案，但是以最大节点的值来区分，还是可以区分出大小的。所以我们从类比建模的角度还是可以看出来这种二分的思想！
为什么是Dijkstra算法？
我们二分答案有三个最重要的东西：
第一：搜索区间
很明显，我们需要搜索所有的点的值，因为每一个点（只要比起点和终点大）就有可能，为何要比起点和终点大呢？废话，如果不比起点和终点大，那想必不是方案中值最大的点！然后我们搜索的区间不是连续的，但是区间的下标是连续的，也就是 1 - n，所以我们的搜索区间的：[1, n]，然后映射到点的值上面去！
第二：check()函数我们需要判断可行解，也就是在二分中判断相对大小！
如何check呢？？我们输入一种二分出来的答案进入check，然后看看能否在这个答案下成功的走到终点，如果可以，那么当然就是可行解咯！
第三：如果可行（或者不可行），我们的状态向哪边转移？
我们设想之前的check()，如果我们的答案过小，很可能就走不出这样的可行方案，因为我们知道，把点值最大的值作为方案是必然能够完成的，因为这样就是全图方案，这必须能够走到终点，否则无论怎么走都到达不了终点！那么如果我们当前的方案可行！说明我们可以把状态向二分较小的方案转移。如果不可行，就说明太小了，就需要向二分较大的方案转移！
再说Dijkstra的作用：
我们在check一个答案的时候，我们假想这个答案就是当前方案的最大点值的点，那么超过这个点值的点我们是一定不能走的，否则就不满足这个设想了！所以我们一开始需要把超过这个点值的点全部标记成不能走的点！然后去跑Dijkstra算法（因为没有负边权），然后在Dijkstra算法下看看能不能在血量消耗完之前走到终点！所以这个Dijkstra是辅助check的！
为什么需要堆优化？
我们的数据规模：n <= 1e4，不用堆优化一次Dijkstra需要O(n^2)
那么，我们二分+Dijkstra需要的开销是：O(n^2*(logn))
计算次数约等于：12*(1e8)=1.2^9加上常数，会超过1e9的限制，于是我们需要优化，但是又不需要很猛的优化，因为其实只超出了一点点，所以就堆优化就够了！
AC代码：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
//#define LL long long
using namespace std;
const int maxn = 10001;
const int inf = 1000000005;
struct Edge{
int to; int cost;
Edge(int t, int c) : to(t), cost(c) {}
};
vector<Edge> G[maxn * 5];
struct Node{
int N_id, N_dis;
Node(int id, int di) : N_id(id), N_dis(di) {}
bool operator< (const Node &n) const { return n.N_dis < N_dis; }
};
int n, m, a, b;
int dis[maxn], f[maxn], s[maxn], c, hp;
bool vis[maxn];
bool Dijkstra(int k){
if(f[1] > k || f[n] > k)
return false;
for(int i = 1;i <= n;++i){
dis[i] = inf;
if(f[i] > k)
vis[i] = true;
else
vis[i] = false;
}
priority_queue<Node> q;
dis[1] = 0;
q.push(Node(1, 0));
while(!q.empty()){
Node Now = q.top(); q.pop();
if(vis[Now.N_id])
continue;
vis[Now.N_id] = true;
for(int k = 0;k < (int)G[Now.N_id].size();++k){
Edge e = G[Now.N_id][k];
if(vis[e.to])
continue;
if(dis[e.to] > Now.N_dis + e.cost){
dis[e.to] = Now.N_dis + e.cost;
q.push(Node(e.to, dis[e.to]));
}
}
}
return dis[n] < hp;
}
int main(){
scanf("%d %d %d", &n, &m, &hp);
for(int i = 1;i <= n;++i){
scanf("%d", &f[i]);
s[i] = f[i];
}
while(m--){
scanf("%d %d %d", &a, &b, &c);
if(a == b)
continue;
G[a].push_back(Edge(b, c));
G[b].push_back(Edge(a, c));
}
sort(s + 1, s + n + 1);
int L = 1, R = n; int ans = s[n];
if(!Dijkstra(ans))
printf("AFK");
else{
while(L <= R){
int mid = (L + R) >> 1;
if(Dijkstra(s[mid])){
ans = s[mid];
R = mid - 1;
}
else
L = mid + 1;
}
printf("%d", ans);
}
return 0;
}