毒瘤45分

毒瘤45分 太毒瘤了

评测记录

#include <bits/stdc++.h>

using namespace std;

int const N = 100010;
int const INF = 1e9 + 10;
int n, m, b, tot, he, ta, f[N], g[N], target[N], prev[N], last[N], v[N], q[N * 10];

void add (int a, int b, int c) {
    target[++tot] = b;
    prev[tot] = last[a];
    last[a] = tot;
    v[tot] = c;
}

bool check (int now) {
    if(f[0] > now || f[n - 1] > now)
    {
        return false;
    }

    for(int i = 0; i < n; i ++ )
    {
        g[i] = INF;

        he = 0, ta = 0, q[0] = 0, g[0] = 0;

        while(he <= ta)
        {
            int x = q[he++], ptr = last[x];

            while(ptr != 0)
            {
                int y = target[ptr];

                if(f[y] <= now && g[y] > g[x] + v[ptr])
                {
                    q[++ta] = y;
                    g[y] = g[x] + v[ptr];
                }

                ptr = prev[ptr];

            }

        } 

    }

    if(g[n] <= b)
    {
        return true;
    }

    return false;

}

int main () {

    scanf("%d%d%d", &n, &m, &b);

    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &f[i]);
    }

    for(int i = 0; i < m; i ++ )
    {
        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        a -- ;
        b -- ;
        c -- ;

        add(a, b, c);
        add(b, a, c);

    }

    int l = 0, r = 1e9 + 1;

    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(check(mid) == true)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }

    if(check(l) == true)
    {
        printf("%d", l);
    }
    else
    {
        if(check(r) == true)
        {
            printf("%d", r);
        }
        else
        {
            printf("AFK");
        }
    }

    return 0;
}