글 읽기 - (벨만 포드)거리가 무한대인 노드를 건너뛰는 것에 문제가 있나요?

plan222 3년 전 0

갱신하기전에 현재 노드까지의 거리가 무한대라면 스킵하도록 하는 부분만 지우니까 정답이 됩니다.

32~33번 째 줄은 -1을 출력해야하는지 판단 하는 곳에서 썼고, 88~89번 째 줄은 벨만 포드를 할 때 썼습니다.

도대체 어떤 경우에 출력이 달라 질 수 있는지 궁금합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>

#define MAX(A,B) A>B?A:B
#define MIN(A,B) A<B?A:B
#define forn(i,n) for(long long i=0;i<n;i++)
#define ll long long
ll gcd(ll a, ll b) { return a % b ? gcd(b, a % b) : b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll wasdX[4] = { 1,0,-1,0 }; ll wasdY[4] = { 0,1,0,-1 };
using namespace std;

/*code start*/
vector<pair<int, int>> edge[101], reverseEdge[101];
ll dist[2][101]; // 0 old 1 new
int From[101];
vector<int> result;
bool forNCcheck[101];
bool visited[101];
queue<int> q;

bool checkNC(int n)
{
	for (int i = 1; i <= n; i++)
	{
		/*if (dist[0][i] == 987654321)
			continue;*/
		for (auto element : edge[i])
		{
			if (dist[0][i] + element.second < dist[0][element.first])
			{
				dist[1][element.first] = dist[0][i] + element.second;
				forNCcheck[element.first] = true;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		dist[0][i] = dist[1][i];
	}
	q.push(n);
	int tmp;
	while (!q.empty())
	{
		tmp = q.front();
		q.pop();
		if (visited[tmp])
			continue;
		visited[tmp] = true;
		if (forNCcheck[tmp])
			return false;
		for (auto element : reverseEdge[tmp])
		{
			if (!visited[element.first])
				q.push(element.first);
		}
	}
	return true;
}

void solve()
{
	int n, m, u, v, w;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		dist[0][i] = 987654321;
		dist[1][i] = 987654321;
	}
	dist[0][1] = 0;
	dist[1][1] = 0;
	forn(i, m)
	{
		cin >> u >> v >> w;
		edge[u].push_back({ v,-w });
		reverseEdge[v].push_back({ u,-w });
	}
	forn(j, n - 1)
	{
		for (int i = 1; i <= n; i++)
		{
			/*if (dist[0][i] == 987654321)
				continue;*/
			for (auto element : edge[i])
			{
				if (dist[0][i] + element.second < dist[0][element.first])
				{
					dist[1][element.first] = dist[0][i] + element.second;
					From[element.first] = i;
				}
			}
		}
		for (int i = 1; i <= n; i++)
		{
			dist[0][i] = dist[1][i];
		}
	}
	if (From[n] == 0 || !checkNC(n))
	{
		cout << "-1";
	}
	else
	{
		int ptr = n;
		while (ptr != 1)
		{
			result.push_back(ptr);
			ptr = From[ptr];
		}
		result.push_back(1);
		for (int i = result.size() - 1; i >= 0; i--)
		{
			cout << result[i] << " ";
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll t = 1;
	//cin >> t;

	while (t--)
	{
		solve();
	}

}