求助

回复帖子

@黑猫_琉璃 2019-05-08 23:25 回复

代码如下,WA第9、10个点。

评测记录

#include<iostream>
#include<cstdio>
#include<queue>
#include<climits>
using namespace std;

const int MAXN = 20005,MAXM = 100010,INF = INT_MAX;
int t,n,m,x,y,z,cnt,head[MAXN],dis[MAXN],cont[MAXN],crt,beu;
bool inq[MAXN];

struct Edge {
    int to;
    int w;
    int nxt;
} l[MAXM*2];

void addEdge(int x,int y,int z){
    cnt++;
    l[cnt].to = y;
    l[cnt].w = z;
    l[cnt].nxt = head[x];
    head[x] = cnt;
} 
bool spfa(){
    queue<int> q;
    crt = 1;
    q.push(crt);
    inq[crt] = true;
    dis[crt] = 0;
    cont[crt] = 1;
    while(q.size()){
        crt = q.front();
        q.pop();
        inq[crt] = false;
        for(int i=head[crt];i;i=l[i].nxt){
            beu = l[i].to;
            if(dis[beu] > (dis[crt] + l[i].w)){
                dis[beu] = dis[crt] + l[i].w;
                if(!inq[beu]){
                    q.push(beu);
                    inq[beu] = true;
                }
                cont[beu] = cont[crt] + 1;
                if(cont[beu] >= n){
                    return true;
                }
            }
        }
    }
    return false;
}
void init(){
    cnt = 0;
    for(int i=1;i<=n;i++){
        head[i] = cont[i] = 0;
        dis[i] = INF;
        inq[i] = false;
    }
}

int main(void){
    //得到数据的组数
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        init();
        //得到这组数据的点数和边数
        scanf("%d%d",&n,&m);
        for(int j=1;j<=m;j++){
            scanf("%d%d%d",&x,&y,&z);
            addEdge(x,y,z);
            if(z >= 0){
                addEdge(y,x,z);
            }
        }
        if(spfa()){
            printf("YE5\n");
        }else{
            printf("N0\n");
        }
    } 
    return 0;
}

望大家指点一二。

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



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