50分求助!!!!
查看原帖
50分求助!!!!
362325
_YUZIhaizhao_楼主2021/8/31 16:12

这道题为什么24分?

嘤嘤嘤蒟蒻呻吟。

恳请大佬指点

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,x,y,val,h[3010],cnt[3010];
int f[3010],e[6010][3],top,wer;
long long out,ans[3010];
bool tag[3010];
queue<int> s;
struct edge
{
    int u;
    int v;
    int w;
    int next;
}g[100001];
void link(int u,int v,int l)
{
    top++;
    g[top].next=f[u];
    g[top].v=v;
    g[top].w=l;
    f[u]=top;
}
bool spfa()
{
    int u,v;
    for(int i=1;i<=n;i++)
        s.push(i);
    while(!s.empty())
    {
        u=s.front();
        s.pop();
        for(int i=f[u];i!=-1;i=g[i].next)
        {
            v=g[i].v;
            if(h[v]>h[u]+g[i].w)
            {
            	s.push(v);
			    h[v]=h[u]+g[i].w;
                cnt[v]++;
                if(cnt[v]>=n)
                    return(true);
            }
        }
    }
    return(false);
}
int main()
{
	scanf("%d",&wer);
    while(wer!=0)
    {
    	top=0;
    	memset(f,-1,sizeof(f));
    	memset(g,0,sizeof(g));
    	memset(h,0,sizeof(h));
	    scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&val);
            if(val>=0)
            {    
			    link(x,y,val);
			    link(y,x,val);
            }
            if(val<0)
                link(x,y,val);
        }
        if(spfa())
            printf("YES\n");
        else
            printf("NO\n");
        wer--;
    }
}
2021/8/31 16:12
加载中...