二分+Spfa(WA36分)

先二分答案

然后最短路

此题不卡spfa所以无伤大雅

用spfa是因为码量小

然而我却WA了qwq

luogu给的数据太大没法调试

求dalao给看看代码qwq

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

struct Edges
{
    int next , to;
    long long key;
}edge[100010];
long long first[10010] , dis[10010] , hp , cnt = 0 , date[10010] , n;
bool vis[10010];
queue <int> que;

void add(int a , int b , int c)
{
    edge[++cnt].to = b , edge[cnt].key = c;
    edge[cnt].next = first[a] , first[a] = cnt;
}

void spfa(int lit)
{
    que.push(1);
    fill(dis , dis + n + 1 , 1e18);
    dis[1] = 0 , vis[1] = 1;
    while(!que.empty())
    {
        int now = que.front();
        que.pop() , vis[now] = 0;
        for(int i = first[now]; i; i = edge[i].next)
        {
            int to = edge[i].to;
            if(date[to] > lit) continue;
            if(dis[now] + edge[i].key < dis[to])
            {
                dis[to] = dis[now] + edge[i].key;
                if(!vis[to]) que.push(to) , vis[to] = 1;
            }
        }
    }
}

bool check(int now)
{
    spfa(now);
    if(dis[n] <= hp) return 1;
    else return 0;
}

int main()
{
    //freopen("test.in" , "r" , stdin);
    long long m , l , r = 0;
    cin >> n >> m >> hp;
    for(int i = 1; i <= n; i++)
    {
        cin >> date[i];
        r = max(r , date[i]);
    }
    l = max(date[1] , date[n]);
    for(int i = 1; i <= n; i++)
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c) , add(b , a , c);
    }
    long long ans = 1e18;
    while(l <= r)
    {
        long long mid = (l + r) / 2;
        if(check(mid)) ans = mid , r = mid - 1;
        else l = mid + 1;
    }
    if(ans < 1e18) cout << ans << endl;
    else cout << "AFK" << endl;
    return 0;
}