1 solutions
-
0
//算法分析:记录某个点的某条路径上的点的数目,如果某条路径上的点的数目超过了n个,那么根据抽屉原理,一定出现了负环 #include<bits/stdc++.h> using namespace std; const int N=2010,M=10010; int h[N],e[M],ne[M],w[M],idx; bool st[N]; int n,m; int dist[N],cnt[N]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } bool spfa() { queue<int> q; memset(dist,0,sizeof dist); for(int i=1;i<=n;i++) //所有点入队 { q.push(i); st[i]=1; } while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) //距离可以变小 { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) //从某个点到当前点的入队次数超过了n(根据抽屉原理,一定又换) { return true; } if(!st[j]) //进入队列之中 { st[j]=1; q.push(j); } } } } return false; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } if(spfa()) cout<<"Yes"; else { cout<<"No"; } return 0; }
- 1
Information
- ID
- 1368
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 5
- Accepted
- 3
- Uploaded By