玄关!!!负环模板全输NO求调
查看原帖
玄关!!!负环模板全输NO求调
1399216
_Gloaming_楼主2024/11/29 11:55
#include<bits/stdc++.h>
using namespace std;
inline int rr()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')
    {if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0')
    {x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=1e3+10;
struct node
{
    int u,v,ne,w;
}e[N*10];
int n,m,tot=0;
int h[N],dis[N],vis[N],cnt[N];
void add(int u,int v,int w)
{
    tot++;
    e[tot].u=u;
    e[tot].v=v;
    e[tot].ne=h[u];
    h[u]=tot;
}
bool spfa()
{
    queue<int> q;
    memset(dis,0x3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[1]=0;vis[1]=1;q.push(1);
    while(!q.empty())
    {
        int a=q.front();vis[a]=0;q.pop();
        for(int i=h[a];i;i=e[i].ne)
        {
            int v=e[i].v;
            if(dis[v]>dis[a]+e[i].w)
            {
                dis[v]=dis[a]+e[i].w;
                if(!vis[v])
                {
                    cnt[v]++;
                    if(cnt[v]>=n)
                        return 1;
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        tot=0;
        memset(e,0,sizeof(e));
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            u=rr();v=rr();w=rr();
            add(u,v,w);
        }
        if(spfa())
            cout<<"yes\n";
        else
            cout<<"no\n";
    }
    return 0;
}
2024/11/29 11:55
加载中...