【警示后人】只WA#13输出5的看这里

xkcdjerry @ 2022-03-21 20:37:26

by drained @ 2022-03-25 21:45:01

感谢

by FReQuenter @ 2022-04-13 17:58:34

感谢

by 喵仔牛奶 @ 2022-04-23 19:18:48

感谢qwq

by Carelessly @ 2022-04-24 15:45:41

感谢qwq

by CH3CHO @ 2022-05-08 21:26:28

我这个是从左边界开始的也wa了qwq

by CH3CHO @ 2022-05-08 21:29:13

@CH3CHO 求大佬指点

#include<bits/stdc++.h>

using namespace std;
typedef pair<int , int > PII;

const int N = 1e6 + 10, M = 5e6 + 10, INF = 0x3f3f3f3f;
typedef long long ll;

ll n, m, b;
ll f[M], w[M];
ll h[N], e[M], ne[M], idx, u[M];
ll dist[N];
bool st[N];

void add (int a, int b, int c)
{
    e[idx] = b, u[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool dj(int tem)
{
    memset(st, 0, sizeof st);
    if(tem < w[1]) return false;

    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + u[i] && f[j] <= tem)
            {
                dist[j] = dist[ver] + u[i];
                heap.push({dist[j], j});
            }
        }
    }

    if(dist[n] == INF) return false;
    if(dist[n] > b) return false;
    return true;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%lld%lld%lld", &n, &m, &b);

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

    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    if(!dj(INF))
    {
        puts("AFK");
        return 0;
    }

    sort(w + 1, w + n + 1);
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(dj(w[mid])) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", w[l]);

    return 0;
}

by carp_oier @ 2023-09-02 17:43:08

跪谢