萌新求助全 WA，SPFA + 二分

P1462 通往奥格瑞玛的道路

一只书虫仔 @ 2020-07-11 17:09:00

听到了说是点权之和二分，但是我写出来的代码没有地方可以用上 f_i（

所以求助一下大佬，在哪里加上 f_i 啊

（并且我这个代码有几个 RE 的 qwq）

#include <bits/stdc++.h>

using namespace std;

struct node {
    int val, next, length;
} e[100086];

int n, m, b, cnt;
int f[10086];
int head[50086];
int dist[50086], sum[50086];
const int inf = 0x3f3f3f3f;

void AddEdge (int u, int v, int w) {
    e[++cnt].val = v;
    e[cnt].next = head[u];
    e[cnt].length = w;
    head[u] = cnt;
}

struct cmp {
    bool operator () (int a, int b) {
        return dist[a] > dist[b];
    }
};

priority_queue <int, vector<int>, cmp> q;

void SPFA () {
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    int s = 1;
    dist[s] = 0;
    sum[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int cur = q.top();
        q.pop();
        sum[cur] = 0;
        for (int p = head[cur]; p > 0; p = e[p].next)
            if (dist[e[p].val] > dist[cur] + e[p].length) {
                dist[e[p].val] = dist[cur] + e[p].length;
                if (!sum[e[p].val]) {
                    q.push(e[p].val);
                    sum[e[p].val] = 1;
                }
            }
    }
}

int main () {
    scanf("%d%d%d", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &f[i]);
    for (int i = 1, u, v, w; i <= n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
    SPFA();
    if (dist[n] <= b) {
        printf("AFK");
        return 0;
    }
    int low = 0, high = 1e9;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (dist[mid] <= b)
            high = mid - 1;
        else
            low = mid + 1;
    }
    printf("%d", low);
    return 0;
}

by 一只书虫仔 @ 2020-07-11 17:09:31

不希望看到无意义回复

by 一只书虫仔 @ 2020-07-11 17:18:49

代码有点锅，改了一下，但最后会直接 RE

#include <bits/stdc++.h>

using namespace std;

struct node {
    int val, next, length;
} e[100086];

int n, m, b, cnt;
int f[10086];
int head[50086];
int dist[50086], sum[50086];
const int inf = 0x3f3f3f3f;

void AddEdge (int u, int v, int w) {
    e[++cnt].val = v;
    e[cnt].next = head[u];
    e[cnt].length = w;
    head[u] = cnt;
}

struct cmp {
    bool operator () (int a, int b) {
        return dist[a] > dist[b];
    }
};

priority_queue <int, vector<int>, cmp> q;

void SPFA () {
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    int s = 1;
    dist[s] = 0;
    sum[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int cur = q.top();
        q.pop();
        sum[cur] = 0;
        for (int p = head[cur]; p > 0; p = e[p].next)
            if (dist[e[p].val] > dist[cur] + e[p].length) {
                dist[e[p].val] = dist[cur] + e[p].length;
                if (!sum[e[p].val]) {
                    q.push(e[p].val);
                    sum[e[p].val] = 1;
                }
            }
    }
}

int main () {
    scanf("%d%d%d", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &f[i]);
    for (int i = 1, u, v, w; i <= n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
    SPFA();
    if (dist[n] > b) {
        printf("AFK");
        return 0;
    }
    int low = 0, high = 1e9;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (dist[mid] > b)
            high = mid - 1;
        else
            low = mid + 1;
    }
    printf("%d", low);
    return 0;
}

by devout @ 2020-07-11 17:21:21

要根据f判断能不能走啊

by Wenoide @ 2020-07-11 17:22:54

@一只书虫仔

应该是二分收取费用的最大值、判断能否到达？

by 一只书虫仔 @ 2020-07-11 17:23:47

@devout @ScanfN 不对啊，判断能不能走的不应该是血量 b 和 w_i 吗

by Wenoide @ 2020-07-11 17:34:31

@一只书虫仔

求“所有城市中最多的一次收取的费用的最小值”，可以枚举“所有城市中最多的一次收取的费用”，找出能够到达的最小值。不难发现这个东西可以二分。

对于二分的每个“最多费用”，都跑一次最短路，求到达所需的最小生命值（最短路径），判断能否达到。

by 一只书虫仔 @ 2020-07-11 17:39:26

@ScanfN 我知道啊，但是应该不是边权和吧，是点权和把

by 一只书虫仔 @ 2020-07-11 17:40:20

@ScanfN 如果是点权和和边权和的处理方式不一样吧

我就想问的就是这个

by Wenoide @ 2020-07-11 17:47:35

@一只书虫仔

题目以前做的，有点忘了

最短路求的就是边权和，这个点权的意义在于判断某条边能不能走。

如果某条边通向的城市点权大于二分的那个“最多费用”，那么这条边就不能用来更新。

by 一只书虫仔 @ 2020-07-11 17:51:10

@ScanfN 哦好的，我再想想

| 下一页