# 已经判断了不连通负环，第3个点还WA

``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const double eps=1e-8;

int n,m,s;
struct edge {
int to;
int w;
};
vector<edge> g[1002];
int X[101001],Y[101001],W[101001];
int d[1002];
queue<int> Q;
bool inq[1002];
int vis[1002];
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>n>>m>>s;
FOR(i,m) {
int x,y,w;
cin>>x>>y>>w;
if (x==y&&w<0) {
cout<<-1<<endl;
return 0;
} else if (x!=y) g[x].pb(edge{y,w});
}
++n;
FOR(i,n-1) {
g[n].pb(edge{i,0});
}
memset(d,0x3f,sizeof d);
d[n]=0;
bool flag=0;
Q.push(n);
inq[n]=1;
vis[n]=1;
n--;
while (Q.size()) {
int t=Q.front();Q.pop();
inq[t]=0;
for (int i=0;i<g[t].size();i++) {
int to=g[t][i].to,w=g[t][i].w;
if (d[to]>d[t]+w) {
d[to]=d[t]+w;
if (!inq[to]) {
Q.push(to);
inq[to]=1;
if (++vis[to]>n) {
flag=1;
break;
}
}
}
}
if (flag) break;
}
if (flag) {
cout<<-1<<endl;
return 0;
}
memset(d,0x3f,sizeof d);
d[s]=0;
while (Q.size()) Q.pop();;
memset(inq,0,sizeof inq);
Q.push(s);
while (Q.size()) {
int t=Q.front();Q.pop();
inq[t]=0;
for (int i=0;i<g[t].size();i++) {
int to=g[t][i].to,w=g[t][i].w;
if (d[to]>d[t]+w) {
d[to]=d[t]+w;
if (!inq[to]) {
Q.push(to);
inq[to]=1;
}
}
}
}
FOR(i,n) {
if (d[i]==inf) cout<<"NoPath"<<endl;
else cout<<d[i]<<endl;
}
return 0;
}
``````

# 2 条评论

• @ 2020-02-08 16:43:17

负环可能没有连接起点

• @ 2018-09-03 14:43:01

我也是

• 1

ID
1053

8

(无)

7075

608

9%

3