WA 90pts on #12, #20 求助
查看原帖
WA 90pts on #12, #20 求助
860817
Starstream楼主2023/12/31 18:53
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 5 * N;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
int stk[M], top;

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

inline bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0, stk[ ++ top] = 0, st[0] = true;

    while (top > 0)
    {
        int t = stk[top -- ];
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] > n + 1) return false;
                if (!st[j])
                {
                    st[j] = true;
                    stk[ ++ top] = j;
                }
            }
        }
    }
    return true;
}

signed main()
{
    int op, a, b, c;
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        add(0, i, 0);

    while (m -- )
    {
        scanf("%d%d%d", &op, &a, &b);
        if (op == 1) scanf("%d", &c), add(a, b, -c);
        else if (op == 2) scanf("%d", &c), add(b, a, c), add(a, b, 0);
        else add(a, b, 0), add(b, a, 0);
    }

    if (!spfa()) puts("No");
    else puts("Yes");

    return 0;
}
2023/12/31 18:53
加载中...