求拍醒-与下载后的用例1输出完全一样,为什么还WA呢?
查看原帖
求拍醒-与下载后的用例1输出完全一样,为什么还WA呢?
767252
emma_ren楼主2024/3/23 13:26

SPFA判负环,freopen执行用例1,输出与output文件完全一样,单个执行与批量执行都对得上,为什么还是WA啊,求指条明路

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int t, n, m, total_edges;
const int MAXN = 2001;
const int MAXM = 6002;
const int INF = 0x7fffffff;
struct edge{
    int v;
    int w;
};
vector<edge> e[MAXN];

bool spfa(int start){

    //到达v点的边数
    int edgesCnt[MAXM] = {0};
    int vis[n+1] = {0};
    int min_dist[n+1] = {0};
    queue<int> q;

    fill(min_dist, min_dist+n+1, INF);
    min_dist[start] = 0;
    q.push(start);
    vis[start] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(auto ed: e[u]){
            int v = ed.v;
            int w = ed.w;
            if(min_dist[v] > min_dist[u] + w){
                min_dist[v] = min_dist[u] + w;
                if(vis[v] == 0){
                    q.push(v);
                    vis[v] = 1;
                }

                //从u到v增加了一条最短路径上的边
                edgesCnt[v] = edgesCnt[u] + 1;

                //一条最短路径的长度最多为n-1条边, 如果存在负环,意味着要绕着负环走无数圈
                //因此当某个点的边数大于n-1(也即>=n)时存在负环 
                if(edgesCnt[v] >=n){
                    return true;
                }
            }
        }
    }
    //处理完所有点
    return false;
}


int main(){
    int u, v, w;
    // freopen("C:\\Users\\86135\\Downloads\\P3385_1.in", "r",stdin);
    cin >> t;

    for(int k=1;k<=t;k++){
        for(int i=1;i<=MAXN;i++){
            if(!e[i].empty()){
                e[i].clear();
            }
        }
        cin >> n >> m;
        for(int i=1;i<=m;i++){
            cin >> u >> v >> w;
            e[u].push_back({v, w});
            if(w >=0){
                e[v].push_back({u, w});
            }
        }
        if(spfa(1)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

用例1输出: YES NO YES YES YES YES YES YES NO YES

2024/3/23 13:26
加载中...