Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Edge{
- int from, to, weight;
- };
- int t;
- int n, m;
- vector<Edge> graph;
- bool isNegative(){
- vector<int> dist;
- dist.resize(n+1, 0);
- dist[1] = 0;
- bool check = false;
- for(int i=1; i<=n; i++){
- check = false;
- for(Edge e: graph){
- if(dist[e.from] != INT_MAX){
- if(dist[e.to]>dist[e.from]+e.weight){
- //cout << "HI" << '\n';
- dist[e.to] = dist[e.from]+e.weight;
- //cout << "i: " << i << ", dist[e.to]: " << dist[e.to] << ", dist[e.from]: " << dist[e.from] << '\n';
- check = true;
- if(i==n){
- return true;
- }
- }
- }
- }
- if(!check) break;
- }
- return false;
- }
- int main(){
- //freopen("negativecycle.in", "r", stdin);
- cin >> t;
- while(t--){
- cin >> n >> m;
- graph.clear();
- graph.resize(m);
- //dist.resize(n+1, INT_MAX);
- for(int i=0; i<m; i++){
- cin >> graph[i].from >> graph[i].to >> graph[i].weight;
- //cout << graph[i].from << ", " << graph[i].to << ", " << graph[i].weight << '\n';
- }
- if(isNegative()){
- cout << "YES" << '\n';
- }else{
- cout << "NO" << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
