Dùng giải thuật Bellman-Ford để xác định xem graph có negative cycle hay không

[Tuong_Le (Tường Lê)]

Xin chào mọi người, em lại rớt test case nữa. Mỗi lần rớt test case mà không biết sai gì nó mệt lắm luôn. Mong mọi người xem code và gợi ý giúp em ạ. Đề bài xác định xem đồ thị có hướng có negative cycle hay không. Có thì trả về 1, không có thì trả về 0. Vector adj lưu các các điểm nối với nhau trong đồ thị. vector Cost là trọng số của các đường tương ứng. Các input điểm đều -1 để thuận tiện lưu trữ trong vector.
Ví dụ:
4 4
1 2 -5
4 1 2
2 3 2
3 1 1
out put: 1.
Đây là code của em:

// Week4Problem2.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int negative_cycle(vector<vector<int> > &adj, vector<vector<int> > &cost) {
	//write your code here
	vector<long long> distance(adj.size());
	
	for (int i = 0; i < distance.size(); i++)
		distance[i] = INT_MAX;
	distance[0] = 0;
	for (int i = 1; i < adj.size(); i++)
	{
		for (int j = 0; j < adj.size(); j++)
		{
			for (int k = 0; k < adj[j].size(); k++)
			{
				// relax:
				if (distance[j]!= INT_MAX && distance[adj[j][k]] > distance[j] + cost[j][k])
				{
					distance[adj[j][k]] = distance[j] + cost[j][k];
				}
			}
		}
	}
	for (int j = 0; j < adj.size(); j++)
	{
		for (int k = 0; k < adj[j].size(); k++)
		{
			// relax:
			if (distance[j] != INT_MAX && distance[adj[j][k]] > distance[j] + cost[j][k])
				return 1;
		}
	}
	return 0;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > adj(n, vector<int>());
	vector<vector<int> > cost(n, vector<int>());
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		adj[x - 1].push_back(y - 1);
		cost[x - 1].push_back(w);
	}
	cout << negative_cycle(adj, cost);
}

[Tuong_Le (Tường Lê)]

Em đã tìm thấy hint: “Try to think of what happens if the starting vertex you chose cannot reach the negative cycle? Maybe you need a different starting vertex or you simply need to explicitly add one?” và đã hoàn thành được bài này!