풀이

#include<iostream>

using namespace std;

int n,m;//입력값



int road[251][251] = {0};

void FloydWarshall() {
	for (int via = 1; via <= n; via++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {		
				 if (road[from][to] > road[from][via] + road[via][to])
					road[from][to] = road[from][via] + road[via][to];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	


	cin >> n >> m;

	for (int i = 1; i <=n; i++)
	{
		for (int j = 1; j <=n; j++)
		{
			road[i][j] = 1000000000;

		}
	}


	int u, v, b;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> b;
		
		road[u][u] = 0;
		road[v][v] = 0;

		road[u][v] = 0;
		if (b == 0)
		{
			road[v][u] = 1;
		}
		else 
		{
			road[v][u] = 0;
		}
			
	}



	FloydWarshall();

	int k;
	cin >> k;
	int s, e;
	for (int i = 0; i < k; i++)
	{
		cin >> s >> e;
		cout << road[s][e]<<'\n';
	}
}

처음에는 못풀어서 다른 사람이 어떻게 풀었는지 코드를 안보고 대충 도입부에 말만 보고 코드를 풀어놓았는데 어쩌다보니 정답비율 낮추는데에 큰 공헌을 했습니다.

처음에는 시간초과라서 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이렇게 3줄을 넣어주니 그다음부터는 다행히 시간초과는 뜨지않지만 계속 틀렸습니다의 연속 퍼레이드라서 다른 사람들은 도대체 어떻게 풀었는지 코드를 볼 수 밖에 없었습니다.

근데 다른 사람들의 코드를 봐도 풀이과정이 똑같았고 진짜 진짜 너무 똑같아서 백준은 나만 왕따시키는게 혹시 아닐까 생각을 했지만 마침내 발견했습니다.

요  road[v][v] =0자식 이 자식 때문에 틀렸습니다. 사실 제가 멍청멍청하게 road[u][u] =0 만을 해준게 잘못이긴하지만 저 자식이 너무 교묘하게 숨어있는게 나빳자나여 

다른 사람들의 코드를 보다보니 괜히 입력부에서 0을 해준것같기도 합니다. 너무 좁게만 보고있었기에 반성해야겠습니다.

https://www.acmicpc.net/problem/11562

#include<iostream>
#include<algorithm>
using namespace std;


int n, m;
bool road[26][26] = { 0 };


char before, after;
string tmp;

void FloydWarshall() {
	for (int via = 0; via < 26; via++) {

		for (int from = 0; from < 26; from++) {
			if (!road[from][via])
				continue;


			for (int to = 0; to < 26; to++) {
				if (!road[from][via])
					continue;


				if (road[from][via] && road[via][to])
					road[from][to] = 1;
				if (!road[from][via] && !road[via][to])
					road[from][to] = 0;
			}
		}
	}
}


int main()
{

	cin >> n;
	for (int i = 0; i < n; i++) 
	{
		cin >> before >> tmp >> after;
		road[before -'a'][after -'a'] = 1;	
	}

	FloydWarshall();

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> before >> tmp >> after;
		if (road[before - 'a'][after - 'a'] == 1)
			printf("T\n");
		else
			printf("F\n");
	}

}

이 문제는 계속 들여다보다가 결국에 못풀어서 풀이를 봐버렸습니다..

풀이를 보니 cin을 쓰면 훨씬 효율적으로 할 수 있는데.. 괜히 scanf를 잡고있다가 입출력에서 다 진을 뺏겨서 오히려 문제에 집중을 못했던것같습니다. 

https://www.acmicpc.net/problem/15723

플로이드 성공

풀이

#include<iostream>
#include<algorithm>
using namespace std;


int n, m;

int road[101][101] = { 0 };


void FloydWarshall() {
	for (int via = 1; via <= n; via++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {
				if (road[from][to] > road[from][via] + road[via][to])
					road[from][to] = road[from][via] + road[via][to];
			}
		}
	}
}


int main()
{
	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (i == j)
				road[i][j] = 0;
			else
			road[i][j] = 20000000;
		}
	}

	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);

		if(road[a][b] > c)
		road[a][b] = c;
	}

	FloydWarshall();

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (road[i][j] == 20000000)
				road[i][j] = 0;
			printf("%d ", road[i][j]);
		}
		printf("\n");
	}
}

한번 틀리고나서 두번째에 맞춘문제입니다. 플로이드와샬 알고리즘이 워낙 명확해서 따로 손을 댄 부분이 없었으나 문제에서 주어진 비용인 100,000 을 최대비용으로 생각하고 초기화를 한게 오답의 원인이었습니다. 

최대비용은 단순히 100,000을 생각하는게 아니라 각 도시마다 걸리는 비용을 생각해야하기에 

도시의 수 * 비용 = 100 * 100,000 을 해야합니다.

저는 단순문제라고 생각했는데 한번 틀렸기때문에 괘씸해서 그냥 20,000,000 해줬습니다. 제 작은 복수입니다.

+) const int MAX = 20000000; 로하고 MAX를 대입하면 효율적이라고한다.

https://www.acmicpc.net/problem/11404