Baekjoon 11562번 백양로 브레이크

문제

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

걸린 시간

01 : 33 : 49 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
int u, v, b;
int k, s, e;
int adj[251][251];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            adj[i][j] = INF;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> b;
        adj[u][v] = 0;
        adj[v][u] = (b == 0 ? 1 : 0);
    }
    for(int i = 1; i <= n; i++)
        adj[i][i] = 0;
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    cin >> k;
    for(int i = 0; i < k; i++){
        cin >> s >> e;
        cout << adj[s][e] << "\n";
    }
    return 0;
}

가중치가 1로 일정한 그래프이므로 bfs 를 통해 탐색한 최단거리 중, 간선의 방향을 바꾸지 않고도 이동할 수 있는 경로를 세어 결과값에서 뺀 후 제출했지만 틀렸습니다 가 출력되었다.

정답을 보니 한 정점에서 다른 정점으로 이동이 불가능할 때 인접 배열의 값을 1로 하여 플로이드 와샬 알고리즘을 돌리면 간단히 정답을 구할 수 있는 문제였다.