求问,spfa不能通过此题吗

P4779 【模板】单源最短路径(标准版)

Geirangerfjard @ 2023-04-02 10:12:04

RT,32pts

#include <iostream>
#include <cstring>
#include <queue>

#define int long long

const int N = 1400100;

using namespace std;

int n, m, s, jud;

int dist[N];

int h[N], ne[N], to[N], e[N], idx;

bool st[N];

queue <int> q;

int qpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if(n & 1) ans *= a;
        n >>= 1;
        a *= a;
    }
    return ans;
}

void add(int a, int b, int w)

{
    to[idx] = b;
    e[idx] = w;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void spfa()

{
    memset(dist, 0x3f, sizeof dist);
    jud = dist[0];
    dist[s] = 0;
    q.push(s);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int b = to[i];
            if (dist[b] > dist[t] + e[i])
            {
                dist[b] = dist[t] + e[i];
                if (!st[b])
                {
                    st[b] = true;
                    q.push(b);
                }
            }
        }
    }
    //if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    //else cout << dist[n] << endl;
}

signed main()

{
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(h, -1, sizeof h);    
    cin >> n >> m >> s;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
        //add(b, a, w);
    }
    spfa();
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[i] == jud) cout << qpow(2, 31) - 1 << " ";
        else cout << dist[i] << " ";
    }
}

by FuckYouJinhai @ 2023-04-02 10:19:12

@Alone_Helpless 是的,本题卡了s↗P↘F↑a↓,如有需要,请移步弱化版。


by Geirangerfjard @ 2023-04-02 10:20:36

@FiveFourierTransform 听说优化能过,但我不会qwq


by FuckYouJinhai @ 2023-04-02 10:23:47

@Alone_Helpless 实用性不强吧,,,

参考这个https://www.zhihu.com/question/292283275/answer/2824896940 ,不过好像要西加加一十七的语言标准


by UncleSam_Died @ 2023-07-10 07:30:59

@Alone_Helpless 能,但要加优化,用SLF能过


by zzb1217 @ 2023-08-04 12:03:52

要加优化


|