dijkstra+二分(二分答案) 70pts

#include<bits/stdc++.h>
#include<climits>
using namespace std;

int edgecnt=0, h[200050];
int n, m;
long long b, fy[200050];
long long dis[200050];
bool dict[200050];
long long inf = LLONG_MAX/3;
long long l, r, mid;

struct Edge
{
    long long w;
    int to, next;
}edge[200050];

struct Node
{
    long long w;
    int pos;
    friend bool operator < (const Node &x, const Node &y)
    {
        return x.w > y.w;
    }
};

priority_queue<Node> q;

void addedge(int u, int v, long long w)
{
    edge[++edgecnt].to = v;
    edge[edgecnt].w = w;
    edge[edgecnt].next = h[u];
    h[u] = edgecnt;
}

void dijkstra(int fylm)
{
    for (int i = 1; i <= n; i++){
        dict[i] = 0; dis[i] = inf;
    }
    dis[1] = 0;
    while (!q.empty()) q.pop();
    q.push((Node) {0, 1});
    while (!q.empty())
    {
        Node zxtmp = q.top();
        q.pop();
        long long expa = zxtmp.pos;
        if (dict[expa]) continue;
        dict[expa] = 1;
        for (int i = h[expa]; i != -1; i = edge[i].next){
            if (fy[edge[i].to] > fylm) continue;
            if (dis[edge[i].to] > dis[expa]+edge[i].w){
                dis[edge[i].to] = dis[expa]+edge[i].w;
                q.push((Node) {dis[edge[i].to], edge[i].to});
            }
        }
    }
}

int main()
{
    scanf("%d%d%lld", &n, &m, &b);
    for (int i = 0; i <= n; i++) h[i] = -1;
    for (int i = 1; i <= n; i++){
        scanf("%lld", &fy[i]); r = max(r, fy[i]);
    }
    l = max(fy[1], fy[n]);
    int u, v;
    long long w;
    for (int i = 0; i <= m-1; i++){
        scanf("%d%d%lld", &u, &v, &w);
        addedge(u, v, w); addedge(v, u, w);
    }
    while (l < r)
    {
        mid = (l+r)/2;
        dijkstra(mid);
        if (dis[n] > b) l = mid+1;
        else r = mid;
    }
    dijkstra(1);
    if (dis[n] > b) printf("%lld", l);
    else printf("AFK");
    return 0;
}

测试点 subtask0:#1,#4,#7 / subtask1:#11 WA

求助qwq