为什么dijkstra可以AC，而SPFA WA #8

rt

SPFA 90:提交记录

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

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, b, h[10010], f[10010], d[10010], ver[N], nxt[N], edge[N], tot, l, r, ans = -1;
bool v[10010];

void add(int u, int v, int w)
{
    ver[++ tot] = v;
    edge[tot] = w;
    nxt[tot] = h[u];
    h[u] = tot;
    ver[++ tot] = u;
    edge[tot] = w;
    nxt[tot] = h[v];
    h[v] = tot;
}

bool SPFA(int k)
{
    if(f[1] > k)return false;
    queue<int> q;
    for(int i = 1; i <= n; ++ i ) d[i] = 1e16;
    memset(v, 0, sizeof(v));
    d[1] = 0;
    v[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for(int i = h[x]; i; i = nxt[i])
        {
            int y = ver[i], z = edge[i];
            if(f[y] > k) continue;
            if(d[y] > d[x] + z)
            {
                d[y] = d[x] + z;
                if(!v[y]) q.push(y), v[y] = 1;
            }
            if(y == n)
            {
                if(d[y] <= b) return true;
                return false;
            }
        }
    }
    return false;
}

inline int read()
{
    int x = 0;
    bool f = true;
    char ch = getchar();
    while(!isdigit(ch)){if(ch == '-') f = false; ch = getchar();}
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f ? x : ~x + 1;
}

signed main() {
    n = read(), m = read(), b = read();
    for(int i = 1; i <= n; ++ i )
    {
        f[i] = read();
        l = min(l, f[i]);
        r = max(r, f[i]);
    }
    for(int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        u = read(), v = read(), w = read();
        add(u, v, w);
    }
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(SPFA(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if(ans == -1) puts("AFK");
    else printf("%lld", ans);
    return 0;
} 

dijkstra 100:提交记录

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

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, b, h[10010], f[10010], d[10010], ver[N], nxt[N], edge[N], tot, l, r, ans = -1;
bool v[10010];

void add(int u, int v, int w)
{
    ver[++ tot] = v;
    edge[tot] = w;
    nxt[tot] = h[u];
    h[u] = tot;
    ver[++ tot] = u;
    edge[tot] = w;
    nxt[tot] = h[v];
    h[v] = tot;
}

bool dijkstra(int k)
{
    if(f[1] > k)return false;
    priority_queue<pair<int, int> > q;
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if(v[x])continue;
        v[x] = 1;
        for(int i = h[x]; i; i = nxt[i])
        {
            int y = ver[i], z = edge[i];
            if(f[y] > k) continue;
            if(d[y] > d[x] + z)
            {
                d[y] = d[x] + z;
                q.push(make_pair(-d[y], y));
            }
            if(y == n)
            {
                if(d[y] <= b) return true;
                return false;
            }
        }
    }
    return false;
}

inline int read()
{
    int x = 0;
    bool f = true;
    char ch = getchar();
    while(!isdigit(ch)){if(ch == '-') f = false; ch = getchar();}
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f ? x : ~x + 1;
}

signed main() {
    n = read(), m = read(), b = read();
    for(int i = 1; i <= n; ++ i )
    {
        f[i] = read();
        l = min(l, f[i]);
        r = max(r, f[i]);
    }
    for(int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        u = read(), v = read(), w = read();
        add(u, v, w);
    }
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(dijkstra(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if(ans == -1) puts("AFK");
    else printf("%lld", ans);
    return 0;
}