[백준 11562] 백양로 브레이크

문제

www.acmicpc.net/problem/11562

 

알고리즘

floyd-warshall

 

풀이

$u$에서 $v$로 갈 때 필요한 최소한의 다리 설치 수를 묻고 있습니다.

 

플로이드-와샬의 특징은 모든 출발지와 도착지에 대해 최단거리를 구할 수 있습니다. 문제의 특징과 잘 맞으며 더군다나 $n$ 제한에서 플로이드-와샬임을 느낄 수 있습니다.

 

처음 모든 $dist$를 큰 값으로 초기화합니다. 만약 양방향 도로가 주어진다면 $dist[u][v]$, $dist [v][u]$를 0으로 설정합니다. 이는 각 정점에서 다른 정점으로 가기 위한 최소한의 다리 설치를 의미합니다. (단, 다리 설치는 단방향 다리에만 추가적으로 설치할 수 있습니다). 반면 단방향 도로가 주어진다면 연결되지 않은 곳만 1로 업데이트해주면 됩니다.

 

초기 셋팅을 위와 같이 하고 플로이드 와샬을 사용하면 배열의 값이 곧 최소한의 설치 수를 의미합니다. 시간 복잡도는 $O(N^3)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, u, v, t, q;
int dist[251][251];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    memset(dist, 0x3f, sizeof(dist));
    cin >> n >> m;
    REP(i, n) dist[i][i] = 0;

    rep(i, m) {
        cin >> u >> v >> t;
        dist[u][v] = 0;
        if (t == 1)
            dist[v][u] = 0;
        else
            dist[v][u] = 1;
    }

    REP(k, n) REP(i, n) if (dist[i][k] != INF) REP(j, n) if (dist[k][j] != INF) {
        if (dist[i][j] > dist[i][k] + dist[k][j])
            dist[i][j] = dist[i][k] + dist[k][j];
    }
    cin >> q;
    while (q--) {
        cin >> u >> v;
        cout << dist[u][v] << '\n';
    }
    return 0;
}