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