蒟蒻求调

只AC了hack的最后两个点

#include <bits/stdc++.h>
const int MAXN = 10000 + 20;

long long n, m, b;
long long Cost[MAXN];

long long tot = 0;
long long head[MAXN * 2];

long long dis[MAXN];
bool vis[MAXN];

long long YXBSB = 0;
long long CNMSB = 0;

long long YXBANS;

struct node
{
    long long dis;
    int pos;

    friend bool operator < (const node &a, const node &b)
    {
        return a.dis > b.dis;
    }

} Node[MAXN * 2];
std::priority_queue<node> Heap;

struct edge
{
    long long w;
    long long val;
    long long pre;

} Edge[MAXN * 10];

void init();

void read();

long long binary_function();

//链式前向星建图
void Graph_Insert(long long x, long long y, long long val);

//用于check函数:检查当图确定时能否到达(最短路)
void dijkstra(long long x);

//检验能否在收费最大值<=x时到达终点
bool check(long long x);

int main()
{
    //基础处理
    init();
    read();

    long long Ans = binary_function();

    printf("%lld" ,Ans);

    return 0;
}

void init()
{
    while(!Heap.empty()) Heap.pop();

    for(int i = 1; i <= n; i++)
    {
        dis[i] = 0x3f3f3f3f;
    }

    memset(vis, false, sizeof(false));
}

void read()
{
    scanf("%lld %lld %lld", &n, &m, &b);

    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &Cost[i]);
        CNMSB = std::max(CNMSB, Cost[i]);
    }

    long long x, y, c;
    for(long long i = 1; i <= m; i++)
    {
        scanf("%lld %lld %lld", &x, &y, &c);
        Graph_Insert(x, y, c);
        Graph_Insert(y, x, c);
    }
    YXBSB = std::max(Cost[1], Cost[n]);
}

void Graph_Insert(long long x, long long y, long long val)
{
    Edge[++tot].w = y,Edge[tot].val = val;

    Edge[tot].pre = head[x];
    head[x] = tot;
}

long long binary_function()
{
    long long Left = YXBSB, Right = CNMSB, Mid;

    while(Left < Right)
    {
        Mid = Left + ((Right - Left) / 2);

        if(check(Mid))
        {
            //YXBANS = Mid;
            //std::cout << YXBANS << std::endl;
            Right = Mid;
        }else{
            Left = Mid + 1;
        }
    }

    return Left;
}

bool check(long long x)
{
    init();

    dijkstra(x);

    if(dis[n] <= b)
    {
        //std::cout << dis[n] << std::endl;
        return true;
    }else{
        //std::cout << dis[n] << std::endl;
        return false;
    }
}

void dijkstra(long long x)
{
    dis[1] = 0;
    if(Cost[1] <= x)
        Heap.push((node){0, 1});

    while(!Heap.empty())
    {
        node Nowdo = Heap.top();
        Heap.pop();

        if(vis[Nowdo.pos])
            continue;
        vis[Nowdo.pos] = true;

        for(int i = head[Nowdo.pos]; i; i = Edge[i].pre)
        {
            if(Cost[Edge[i].w] > x) continue;
            if(vis[Edge[i].w]) continue;
            if(dis[Edge[i].w] > dis[Nowdo.pos] + Edge[i].val)
            {
                dis[Edge[i].w] = dis[Nowdo.pos] + Edge[i].val;

                Heap.push((node){dis[Edge[i].w], Edge[i].w});
            }
        }
    }
}

/*
6 7 10
1
4
5
3
6
2
1 2 3
2 5 1
2 4 5
2 6 4
4 6 2
3 6 2
1 3 2

4
*/

玄关