BOJ 11562: 백양로 브레이크

#BOJ 11562: 백양로 브레이크

1507번: 궁금한 민호

#풀이

다리가 양방향이 있고 일방통행이 있다.

 

문제는 돌아올 때 일방통행을 얼마나 거치는 지 출력하는지 문제이다.

 

입력에서 b를 통해 일방통행인지 양방향인지 알 수 있다.

 

입력 u,v,b

b가 0이면 일방통행 1이면 양방향

하지만 b에 상관없이 d[u][v] = 0; 저장해야 하고

일방통행이면 d[u][v] = 1, 양방향이면 0 을 저장한다.

 

플로이드 알고리즘을 사용하여 최소 비용 경로를 찾을 때

일방통행이 아닌 양방향을 우선 적으로 경로로 찾는다. 양방향이 비용이 적으므로

 

일방통행으로 경로를 찾으면 비용이 생기지만 비용이 1이므로 일방통행을 거쳐온 개수가 된다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m;
int d[251][251]; // 원본
const int INF = 0x3f3f3f3f;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	
	for(int i =1; i <=n; i++){
		fill(d[i]+1, d[i] + n+1, INF);
		d[i][i] = 0;
	}
		
		
	for(int i = 0; i < m; i++){
		int u, v;
		bool b; // b==0 일방통행 1 양방향
		cin >> u >> v >> b;
		d[u][v] = 0;
		d[v][u] = !b;
		
	}
	
	for(int k = 1; k <=n; k++){
		for(int i = 1; i<=n;i++){
			for(int j = 1; j <=n; j++){
				if(d[i][j] > d[i][k] + d[k][j])
				{
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
	
	int z = 0;
	cin >> z;
	for(int i = 0; i < z; i++){
		int a, b;
		cin >> a >> b;
		cout << d[a][b]<<'\n';
	}	
	return 0;
}