最后一个点过不去,感觉是判断负环那里错了,谁能帮我看看
查看原帖
最后一个点过不去,感觉是判断负环那里错了,谁能帮我看看
1140371
ruanertanjing楼主2024/5/24 15:03

我判断负环是这样子写的,请问那里的问题

 num[t] = num[dian] + 1;
if (num[t] > n/**/)//因为加了0号节点,所以有n + 1个点
{
	return false;
}
const int N = 5e3 + 5;
const int M = 5e3 + 5;

int head[N];
int cnt;
int vis[N];
int dis[N];
int num[N];

int n, m;

struct EDGE
{
    int v;
    int w;
    int next;
}EDGE[M + N];

void add(int u, int v, int w)
{
    cnt++;
    EDGE[cnt].v = v;
    EDGE[cnt].w = w;
    EDGE[cnt].next = head[u];
    head[u] = cnt;
}

bool SPFA(int s)
{
    queue<int>que;
    memset(dis, 0x3f3f3f, sizeof(dis));
    dis[s] = 0;
    //memset(vis, 0, sizeof(vis));
    que.push(s);
    vis[s] = 1;
    num[s]++;

    while (!que.empty())
    {
        int dian = que.front();
        que.pop();
        vis[dian] = 0;

        for (int i = head[dian]; i; i = EDGE[i].next)
        {
            int t = EDGE[i].v;
            int w = EDGE[i].w;

            if (dis[t] > dis[dian] + w)
            {
                dis[t] = dis[dian] + w;
                num[t] = num[dian] + 1;
                if (num[t] > n/**/)
                {
                    return false;
                }

                if (vis[t] != 1)
                {
                    vis[t] = 1;
                    que.push(t);
                }
            }
        }
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    int u, v, c;
    while (m--)
    {
        cin >> v >> u >> c;
        add(u, v, c);
    }

    for (int i = 1; i <= n; i++)
        add(0, i, 0);
    if (SPFA(0))
    {
        for (int i = 1; i <= n; i++)
            cout << dis[i] << " ";
    }
    else
    {
        cout << "NO" << endl;
    }
}

int main()
{
    solve();
    return 0;
}
2024/5/24 15:03
加载中...