• 板块灌水区
  • 楼主_YUZIhaizhao_
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/10/9 19:07
  • 上次更新2023/11/4 04:15:34
查看原帖
362325
_YUZIhaizhao_楼主2021/10/9 19:07

负环判断哪里错了(大佬快帮忙蒟蒻)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int m,n,tot,head[100001],vis[100001];
int cnt[100001],h[100001];
queue<int> q;
struct edge
{
    int u,v,w,next;
}g[100001];
inline void add(int u,int v,int w)
{
    tot++;
    g[tot].v=v;
    g[tot].w=w;
    g[tot].next=head[u];
    head[u]=tot;
}
inline bool spfa()
{
    vis[1]=1;
    h[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=g[i].next)
        {
            int v=g[i].v;
            if(h[v]>h[u]+g[i].w)
            {
                h[v]=h[u]+g[i].w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=m)
                    return(true);
            }
        }
    }
    return(false);
}
int main()
{
    memset(h,0x3f3f3f3f,sizeof(h));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(spfa())
        printf("Yes\n");
    else
        printf("No\n");
}
2021/10/9 19:07
加载中...