luogu1462 通往奥格瑞玛的道路

题目大意

　　给出一个有边权和点权的无向图，规定路径长度为路径经过的边权和。求出这么一条从起点到终点的路径，它的长度小于等于给出的长度限制（条件1），且经过的点权最大的点的点权是所有满足条件1的路径中的最小的。

题解

　　图论题我没怎么接触过需要用到反演思想的，然而这道题就是。我们发现这个图有这么一个单调性：选的点数越多，子图中起点到终点的最短路径就会越短。因此我们每次枚举一个节点，将点权小于等于该节点的节点都纳入子图（显然该节点的点权越大，加入子图中的节点数越多），看看图中的最短路径长度是否小于等于长度限制。显然枚举的节点的点权越大，满足限制条件可能性越大，反之越小。这样我们就可以二分了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX_NODE = 10010, MAX_EDGE = 100010, INF = 0x3f3f3f3f;
int DistLimit;

struct Node;
struct Edge;

struct Node
{
    Edge *Head;
    int Weight, Dist;
    bool Done, InGraph;
}_nodes[MAX_NODE], *Sorted[MAX_NODE];
int TotNode;

struct Edge
{
    Node *To;
    Edge *Next;
    int Weight;
}_edges[MAX_EDGE];
int _eCount;

struct CmpPNode
{
    bool operator () (Node *a, Node *b)
    {
        return a->Dist > b->Dist;
    }
};

bool Cmp(Node *a, Node *b)
{
    return a->Weight < b->Weight;
}

void AddEdge(Node *from, Node *to, int w)
{
    Edge *e = _edges + ++_eCount;
    e->To = to;
    e->Weight = w;
    e->Next = from->Head;
    from->Head = e;
}

void Build(int uId, int vId, int w)
{
    Node *u = _nodes + uId, *v = _nodes + vId;
    AddEdge(u, v, w);
    AddEdge(v, u, w);
}

struct HeapNode
{
    long long Dist;
    Node *CurNode;
 
    HeapNode(long long dist, Node *curNode):Dist(dist), CurNode(curNode){}
 
    bool operator < (const HeapNode& a) const
    {
        return Dist > a.Dist;
    }
};
 
void Dijkstra()
{
    for (int i = 1; i <= TotNode; i++)
    {
        _nodes[i].Dist = INF;
        _nodes[i].Done = false;
    }
    if (!_nodes[1].InGraph)
        return;
    _nodes[1].Dist = 0;
    static priority_queue<HeapNode> q;
    q.push(HeapNode(0, _nodes + 1));
    while (!q.empty())
    {
        HeapNode temp = q.top();
        q.pop();
        Node *cur = temp.CurNode;
        if (cur->Done)
            continue;
        cur->Done = true;
        for (Edge *e = cur->Head; e; e = e->Next)
        {
            if (!e->To->InGraph)
                continue;
            if (cur->Dist + e->Weight < e->To->Dist)
            {
                e->To->Dist = cur->Dist + e->Weight;
                q.push(HeapNode(e->To->Dist, e->To));
            }
        }
    }
}

bool Alive(int x)
{
    for (int i = 1; i <= x; i++)
        Sorted[i]->InGraph = true;
    for (int i = x + 1; i <= TotNode; i++)
        Sorted[i]->InGraph = false;
    Dijkstra();
    return _nodes[TotNode].Dist <= DistLimit;
}

int LowerBound(int l, int r, bool (*InRange) (int))
{
    if (!InRange(r))
        return -1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (InRange(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main()
{
    int totEdge;
    scanf("%d%d%d", &TotNode, &totEdge, &DistLimit);
    for (int i = 1; i <= TotNode; i++)
        scanf("%d", &_nodes[i].Weight);
    for (int i = 1; i <= totEdge; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        Build(u, v, w);
    }
    for (int i = 1; i <= TotNode; i++)
        Sorted[i] = _nodes + i;
    sort(Sorted + 1, Sorted + TotNode + 1, Cmp);
    int p = LowerBound(1, TotNode, Alive);
    if (p == -1)
        printf("AFK
");
    else
        printf("%d
", Sorted[p]->Weight);
    return 0;
}