글 읽기 - 풀어도 풀어도 안풀리네요..도와주세요ㅠㅠ

his130 6년 전 0

우선 문제에 조건에 따라

간선값과 도착점을 합성해서, 새로운 간선값을 만들었습니다.

예를 들어 1에서 2까지 비용이 20이고, 2에 갔을 때 버는 돈이 10 이면 간선이 -10이 되도록 하였습니다.

그 다음 플로이드 알고리즘을 통해서 연결되어 있는지 여부를 파악했습니다.

그 다음 벨만포드 알고리즘을 사용했습니다.

그래서 음수 싸이클이 존재하는 경우와 존재하지 않는 경우로 나눠서 답을 출력했습니다.

음수 싸이클이 존재할 때, 그 값들을 st 벡터 배열에 넣었습니다.

그리고 while문을 통해서 값들 중 하나라도 목적 및 출발점과 연결되어 있으면 canReach를 true 로 만들고

싸이클 내의 정점이 목적지에 연결되어있으면 무한대 이므로 Gee를 출력했습니다.

연결 되어 있지 않을 때, 다른 길을 통해 갈 수 있으면 그 값을, 아니면 gg를 출력하도록 하였습니다.

모든 예제랑, 질문 게시판 반례값도 맞는데 도통 모르겠습니다..ㅠㅠㅠ

#include<iostream>
#include<vector>

using namespace std;
const int INF = 987654321;
bool D[101][101];
int main()
{
	//freopen("input.txt", "r", stdin);
	int n, s, e, m;
	scanf("%d %d %d %d", &n, &s, &e, &m);

	vector<vector<int>> v(n, vector<int>(n,INF));
	vector<int> x(n);
	vector<long long> upper(n,INF);
	while (m--)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v[a][b] = -c;
		D[a][b] = true;
	}
	
	for (int i = 0; i < n; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		x[i] = tmp;
		for (int j = 0; j < n; j++)
		{
			if (v[j][i] == INF) { continue; };
			
			v[j][i] += tmp;
		}
	}
	// 플로이드워셜

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				D[i][j] = D[i][j] || (D[i][k] && D[k][k]);
			}
		}
	}


	// 벨만포드
	bool update;
	upper[s] = -x[s];
	bool cango = false;
	vector<int> st;

	for (int i = 0; i < n; i++)
	{
		update = false;
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k <n; k++)
			{
				int next = k;
				int cost = -v[j][k];

				if (v[j][k] == INF) { continue; }

				if (upper[next] > upper[j] + cost  && upper[j] != INF)
				{
					upper[next] = upper[j] + cost;
					update = true;
					if (i == n - 1)
					{
						st.push_back(next);
					}
				}
			}
		}

		if (!update)
		{
			break;
		}
	}



	if (update)
	{
		bool canReach = false;
		bool canReach2 = false;
		while (!st.empty())
		{
			int t = st.back();

			st.pop_back();
			
			if (D[t][e])
			{
				canReach = true;
			}
			if (D[s][t])
			{
				canReach2 = true;
			}

			if (canReach && canReach2)
			{
				break;
			}
		}

		if (canReach && canReach2)
		{
			printf("Gee\n");
		}
		else 
		{
			if (upper[e] >= INF)
			{
				printf("gg\n");
			}
			else
			{
				printf("%lld\n", -upper[e]);
			}
		}
	}
	else
	{
		if (upper[e] >= INF)
		{
			printf("gg\n");
		}
		else
		{	
			printf("%lld\n", -upper[e]);
		}
	}
	


	return 0;
}

댓글을 작성하려면 로그인해야 합니다.