{"id":"679f510b-2c36-4c8b-b833-22e4b0e8be90","name":"Negative Weight Cycle Detection","description":"You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge.\r\n\r\nTask is to find if it contains a negative weight cycle or not.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.","outputFormat":"Print 1 if it contains a negative weight cycle else print 0.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n0&lt;= ai, bi &lt;= N-1\r\n1&lt;= wi &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint isNegativeWeightCycle(int n,vector<vector<int>>&edges)\n{\n \n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n\n vector<vector<int>> edges(m,vector<int>(3));\n \n for(int i=0;i<m;i++){\n int x,y,z;\n cin>>x>>y>>z;\n \n edges[i][0]=x;\n edges[i][1]=y;\n edges[i][2]=z;\n \n }\n \n cout<<isNegativeWeightCycle(n, edges);\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\n\t\t BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tint[][] edges = new int[m][3];\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tedges[i][0] = Integer.parseInt(st[0]);\n\t\t\tedges[i][1] = Integer.parseInt(st[1]);\n\t\t\tedges[i][2] = Integer.parseInt(st[2]);\n\t\t}\n\t\tSystem.out.println(isNegativeWeightCycle(n, edges));\n\t}\n\n\tpublic static int isNegativeWeightCycle(int n, int[][] edges) {\n\t\t\n\t}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n0 1 -1\r\n1 2 -4\r\n2 0 3","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"41c4f94e-d839-4fce-b092-4b41b51bb856","name":"Negative Weight Cycle Detection","slug":"negative-weight-cycle-detection","type":1}],"next":{"id":"d4fb9040-c0ef-400a-ba49-78083e9ed563","name":"Negative weight Cycle detection MCQ","type":0,"slug":"negative-weight-cycle-detection-mcq"},"prev":{"id":"f0bcb6a2-d69b-4f7c-af99-25f1003a7934","name":"Bellman Ford","type":3,"slug":"bellman-ford"}}}

Negative Weight Cycle Detection

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Task is to find if it contains a negative weight cycle or not.

{"id":"679f510b-2c36-4c8b-b833-22e4b0e8be90","name":"Negative Weight Cycle Detection","description":"You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge.\r\n\r\nTask is to find if it contains a negative weight cycle or not.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.","outputFormat":"Print 1 if it contains a negative weight cycle else print 0.","constraints":"1&lt;= N &lt;= 10^4\r\n1&lt;= M &lt;= 10^6\r\n0&lt;= ai, bi &lt;= N-1\r\n1&lt;= wi &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint isNegativeWeightCycle(int n,vector<vector<int>>&edges)\n{\n \n}\n\nint main(){\n \n int n,m;\n cin>>n>>m;\n\n vector<vector<int>> edges(m,vector<int>(3));\n \n for(int i=0;i<m;i++){\n int x,y,z;\n cin>>x>>y>>z;\n \n edges[i][0]=x;\n edges[i][1]=y;\n edges[i][2]=z;\n \n }\n \n cout<<isNegativeWeightCycle(n, edges);\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\n\t\t BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tint[][] edges = new int[m][3];\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tedges[i][0] = Integer.parseInt(st[0]);\n\t\t\tedges[i][1] = Integer.parseInt(st[1]);\n\t\t\tedges[i][2] = Integer.parseInt(st[2]);\n\t\t}\n\t\tSystem.out.println(isNegativeWeightCycle(n, edges));\n\t}\n\n\tpublic static int isNegativeWeightCycle(int n, int[][] edges) {\n\t\t\n\t}\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 3\r\n0 1 -1\r\n1 2 -4\r\n2 0 3","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"41c4f94e-d839-4fce-b092-4b41b51bb856","name":"Negative Weight Cycle Detection","slug":"negative-weight-cycle-detection","type":1}],"next":{"id":"d4fb9040-c0ef-400a-ba49-78083e9ed563","name":"Negative weight Cycle detection MCQ","type":0,"slug":"negative-weight-cycle-detection-mcq"},"prev":{"id":"f0bcb6a2-d69b-4f7c-af99-25f1003a7934","name":"Bellman Ford","type":3,"slug":"bellman-ford"}}}
plane

Editor


Loading...

Negative Weight Cycle Detection

easy

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Task is to find if it contains a negative weight cycle or not.

Constraints

1<= N <= 10^4 1<= M <= 10^6 0<= ai, bi <= N-1 1<= wi <= 1000

Format

Input

First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.

Output

Print 1 if it contains a negative weight cycle else print 0.

Example

Sample Input

3 3 0 1 -1 1 2 -4 2 0 3

Sample Output

1

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode