100pts,hack没过WA on #12求调
查看原帖
100pts,hack没过WA on #12求调
782609
Wmz1220楼主2025/7/3 11:23

code

#include <cstdio>
#include <cctype>
#include <bitset>
#include <cstring>

using namespace std;

const int N = 2e3 + 10, M = 6e3 + 10;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N], cnt[N], hh, tt;
bitset<N> st;

inline void add(register int a, register int b, register int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

inline void init()
{
    hh = 0, tt = 1, idx = 0;
    memset(h, -1, sizeof h);
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0, sizeof dist);
    st.reset();
}

inline int spfa()
{
    for (register int i = 1; i <= n; i ++ )
    {
        q[tt ++ ] = i;
        if (tt == N)
            tt = 0;
        st[i] = 1;
    }

    while (hh != tt)
    {
        register int u = q[hh ++ ];
        if (hh == N)
            hh = 0;
        st[u] = 0;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            register int j = e[i];
            if (dist[j] > dist[u] + w[i])
            {
                dist[j] = dist[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n)
                    return 1;

                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = 1;
                }
            }
        }
    }

    return 0;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    qwq = x * f;
    return;
}

int main()
{
    register int T;
    read(T);

    while (T -- )
    {
        init();

        read(n), read(m);

        for (register int i = 1, a, b, c; i <= m; i ++ )
        {
            read(a), read(b), read(c);
            if (c < 0)
                add(a, b, c);
            else add(a, b, c), add(b, a, c);
        }

        if (spfa())
            puts("YES");
        else puts("NO");
    }

    return 0;
}
2025/7/3 11:23
加载中...