BOJ 11562 - 백양로 브레이크

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int dist[251][251];

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dist[i][j] = i == j ? 0 : INF;

	for (int i = 0, u, v; i < m; i++) {
		bool w;
		cin >> u >> v >> w;
		if (w == 0) {
			dist[u - 1][v - 1] = 0;
			dist[v - 1][u - 1] = 1;
		}
		else {
			dist[u - 1][v - 1] = dist[v - 1][u - 1] = 0;
		}
	}
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	int tc; scanf("%d", &tc);
	while (tc--) {
		int a, b; scanf("%d %d", &a, &b);
		printf("%d\n", dist[a - 1][b - 1]);
	}
}

푼지 오래돼서 정확하게 기억이 안나지만..

 

단방향 통로 = 비용1, 양방향 통로= 비용0 으로 생각해서

플로이드 와샬을 돌리면 된다.