萌新求助全 WA，SPFA + 二分

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

#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 81179332_ @ 2020-07-11 21:51:58

@一只书虫仔 改好了。

#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;

int now = 1e9;
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 (f[e[p].val] <= now && 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 <= m; 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,ans = 1e9;
    while (low <= high) {
        int mid = (low + high) / 2;
        now = mid,SPFA();
        if (dist[n] <= b)
            high = mid - 1,ans = min(ans,mid);
        else
            low = mid + 1;
    }
    printf("%d", ans);
    return 0;
}

把低级错误改好了再求助会更好吧，您的读入都把 m 打成 n 啦

我们要求的是最大的点权最小，二分这个最大的点权，则所有点权比二分的 mid 还大的点显然是不能走的，因为我们要保证 mid 是最大的点权

所以我们把不能走的点去掉，每二分一个 mid，跑一遍 SPFA，求一下从 1 到 n 的最短路，如果最短路 <= b，即血量可以支持走到终点，则该 mid 合法，再尝试更小的，否则不合法，尝试更大的

另外 SPFA 最好还是不要写的两不像把。。

by 一只书虫仔 @ 2020-07-11 22:01:18

@81179332_ 嗯，好的，谢谢！

by 一只书虫仔 @ 2020-07-11 22:05:37

@81179332_ SPFA 大概就是我打模板的时候就按照优先队列打的，然后就改不过来了（