哪里错了??

回复帖子

@charliegong 2019-05-12 22:12 回复

9就是不对??

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#define MAXN 1000080
using namespace std;
struct node{
    int v,c;
    int next;
}e[MAXN];
int h[MAXN],tot;
void addEdge(int u,int v,int c){
    tot++;
    e[tot].v=v;e[tot].c=c;e[tot].next=h[u];h[u]=tot;
}
//bool bellmanfors(){
//  int flag=false;
//  for(int k=1;k<=n;k++){
//      for(int i=1;i<=n;i++){
//          if(dis[i]==INF) continue;
//          for(int j=h[i];j;j=e[j].next){
//              if(dis[e[j].v]>dis[i]+e[j].c){
//                  dis[e[j].v]=dis[i]+e[j].c;
//                  flag=true;
//              }
//          }
//      }
//  }
//  return flag;
//}
int q[MAXN*2],num[MAXN],dis[MAXN],n,m;
bool in[MAXN];
bool SPFA(int s){
    int front=0,rear=0;
    memset(num,0,sizeof(num));
    memset(dis,0x3f3f3f,sizeof(dis));
    memset(in,false,sizeof(in));
    q[rear++]=s;dis[s]=0;in[s]=true;num[s]=1;
    while(front<rear){
        int u=q[front++];in[u]=false;
        for(int j=h[u];j;j=e[j].next){
            int v=e[j].v;
            if(dis[v]>dis[u]+e[j].c){
                dis[v]=dis[u]+e[j].c;
                if(!in[v]){
                    in[v]=true;
                    num[v]++;
                    q[rear++]=v;
                    if(num[v]>n) return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    freopen("cc.out","w",stdout);
    int T;
    cin>>T;
    while(T--){
        memset(h,0,sizeof(h));
        memset(q,0,sizeof(q));
        tot=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            addEdge(a,b,c);
            if(c>=0) addEdge(b,a,c);
        }
        if(SPFA(1))cout<<"YE5\n";
        else cout<<"N0\n";
    }
    return 0;
}

9输出:

YE5 N0 YE5 YE5 YE5 YE5 N0 YE5 YE5 YE5

https://www.luogu.org/recordnew/show/18999768

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。