BOJ 11562 백양로 브레이크

사용한 알고리즘

플로이드 와샬

알고리즘 설명

일반통행인 경우, 양방향인 경우와 연결되지 않은 경우 3가지 형태로 구현된다.
두 노드가 연결되지 않는 경우 adj의 값을 초기값인 -1로 설정한다.
위에서 양방향인 경우에는 u->v와 v->u 값을 0으로 설정해준다.
일반 통행인 경우 u->v는 0으로, v->u은 1로 설정한다. v->u 값을 1로 설정하여 일반통행으로 바꿔야 하는 값을 표현할 수 있다.
위와 같이 그래프를 구성한 뒤, 플로이드 와샬 알고리즘을 적용한다.
각 질문에 대한 값을 출력한다.

풀이

// baekjoon 11562 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N=251;

int N, M, u, v, b, K, s, e;
int adj[MAX_N][MAX_N];

int main() {
	memset(adj, -1, sizeof(adj));
	scanf("%d%d", &N, &M);
	for (int i=1; i<=N; i++) adj[i][i]=0;

	// 그래프 구성하기
	while (M--) {
		scanf("%d%d%d", &u, &v, &b);
		adj[u][v]=0;
		adj[v][u]=!b; // 일반통행인 경우 1, 양방향인 경우 0
	}

	for (int k=1; k<=N; k++) {
		for (int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if (i == j) continue;
				// i->k 또는 k->j 간에 연결이 없는 경우
				if (adj[i][k] == -1 || adj[k][j] == -1) continue;
				// i->j가 정해지지 않은 경우, 또는 (i->k, k->j) 경로가 (i->j) 경로보다 작은 경우
				if (adj[i][j] == -1 || (adj[i][j] > adj[i][k] + adj[k][j]))
					adj[i][j] = adj[i][k] + adj[k][j];
			}
		}
	}

	// 결과 출력
	scanf("%d", &K);
	while (K--) {
		scanf("%d%d", &s, &e);
		printf("%d\n", adj[s][e]);
	}
	return 0;
}