백준 1613 역사

www.acmicpc.net/problem/1613

1613번: 역사

시관초과는 cintie(null) 로 해결

#include <iostream>


using namespace std;


int arr[401][401]; //bool로 해보려고 했는데 이번경우는 출력이 3개나되서


int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, k;

	cin >> n >> k;

	int tmp1, tmp2;
	for (int i = 1; i <= k; i++)
	{
		cin >> tmp1 >> tmp2;
		arr[tmp1][tmp2] = -1;//전후관계는 있지만, 이경우 tmp1이 먼저 발생하므로 tmp2-->tmp1기준은 늦게 발생하여 -1을 넣어봄
		arr[tmp2][tmp1] = 1;  //앞사건이 먼저 일어남  1일때는 먼저 
	}
	

	for (int i = 1; i <= n; i++)
	{
	
		for (int j= 1; j <= n; j++)
		{

			for (int k = 1; k <= n; k++)
			{
				if (i == j || j == k || i == k)continue;

				else
				{
					if (arr[j][i] != 0 && arr[i][k] != 0)
					{
						//경로는 있는데 음..arr[j][k]이부분이 음
						if (arr[j][i] == 1 && arr[i][k] == 1)arr[j][k] = 1;
						else if (arr[j][i] == -1 && arr[i][k] == -1)arr[j][k] = -1;

					}
				}

			}

		}

	}

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1 >> tmp2;
		cout << arr[tmp1][tmp2] << '\n';
	}



}

플로이드 와샬기법을 활용했다

처음엔 bool로 풀려고 하였으나 까다로운게 먼저 발생될때와 후에발생 혹은 모를때 로 출력값이 3가지 경우가 있어서

int형 배열에 1,-1,0을 저장하였다

플로이드 와샬관련 포스팅은 전에도 하였으니 생략하겠다