求助 Dij + 二分 70pts #8 #10 #11 #13

P1462 通往奥格瑞玛的道路

Sora1336 @ 2022-09-06 20:54:30

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 5e4 + 5;
const int inf = 0x3f3f3f3f;

struct E {
    int nxt, to, val;
} e[maxn << 1];
int n, m, k, head[maxn], cnt, dis[maxn], a[maxn];
bool vis[maxn];

void add(int x, int y, int z) {
    e[++ cnt].to = y;
    e[cnt].val = z;
    e[cnt].nxt = head[x];
    head[x] = cnt;
} 

struct node {
    int pos, w;
    friend bool operator < (node a, node b) {
        return a.w > b.w;
    }
} tmp;

priority_queue<node> q;

bool judge(int qwe) {
    for(int i = 1; i <= n; i ++) 
        dis[i] = -1;
    memset(vis, 0, sizeof(vis));
    dis[1] = k;
    tmp.pos = 1, tmp.w = k;
    q.push(tmp);
    while(!q.empty()) {
        int u = q.top().pos;
        int d = q.top().w;
        q.pop();
        if(dis[u]!=d) continue;
        if(vis[u]) continue;
        else vis[u] = 1;
        for(int i = head[u]; i; i = e[i].nxt) {
            if(a[e[i].to] > qwe) continue;
            if(dis[e[i].to] < dis[u] - e[i].val && dis[u] - e[i].val >= 0) {
                dis[e[i].to] = dis[u] - e[i].val;
                tmp.pos = e[i].to, tmp.w = dis[e[i].to];
                q.push(tmp); 
            }
        }
    }
    return (dis[n] != -1);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    int l = inf, r = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d",a + i);
        l = min(l, a[i]);
        r = max(r, a[i]);
    }
    int flg = r;
    for(int i = 1, a, b, c; i <= m; i ++) {
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
        add(b, a, c);
    }
    while(l - 1 < r) {
        int mid = l + r >> 1;
        if(judge(mid)) r = mid - 1;
        else l = mid + 1;
    }
    if(l == flg + 1) cout << "AFK" << endl;
    else cout << l << endl;
}

by Haber @ 2022-09-06 21:10:26

可以尝试使用 l=0,r=0x3f3f3f3f 试一下?


by Sora1336 @ 2022-09-06 21:14:56

@Habers 没用/kk


by Haber @ 2022-09-06 21:24:52

@Sora1336 您为啥 dis 赋成 -1 ?


by Haber @ 2022-09-06 21:25:37

阿西,这波 Dij 完全没看懂hh。


|