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

문제 링크 : [백준]백양로 브레이크(11562)

문제 설명

N개의 노드가 있고, M개의 간선 정보가 주어집니다.
간선은 단방향인 것도 있고, 양방향인 것도 있습니다.
주어진 상황에서 K개의 질의가 주어지는데, 출발지 S에서 도착지 E로 가는데 주어진 간선 중 단방향인 간선 몇개를 양방향으로 바꾸어야 도착할 수 있는지 그 최소값을 구하세요.

입력

N(노드의 갯수, 1 <= N <= 250)
M(간선의 갯수, 1 <= M <= N * (N - 1) / 2)
S_i E_i D_i(출발지, 도착지, 양방향 여부)
K(질의 갯수, 1 <= K <= 30,000)
S_i E_i(출발지, 도착지)

4 3
1 2 0
2 3 1
3 4 0
7
1 1
1 2
2 1
1 4
4 1
2 3
4 3

출력

0
0
1
0
2
0
1

카테고리

#플로이드와샬

시간 복잡도 상한

O(N³)

해결 방법

1. N³의 시간복잡도까지 사용 할 수 있으며, 최단거리와 비슷한 풀이 방법으로 풀 수 있을 것 같으니 플로이드 와샬을 의심해봅니다.
2. 플로이드 와샬은 출발지에서 도착지까지의 최단거리를 구하는 것이나, 여기서 구하고자 하는 것은 단방향 간선을 양방향 간선으로 몇개를 바꾸어야 하는지 입니다.
3. 그렇다면 단방향 간선을 양방향 간선으로 바꾸는 것을 비용으로 생각해봅니다.
4. 인접행렬을 만들 때, 정방향 간선의 비용은 0, 역방향 간선의 비용은 1로 합니다.
5. 처음부터 양방향이 오면 둘다 0으로 해줍니다.
6. 그렇게 인접행렬이 완성 된다면, 플로이드 와샬을 통해 모든 쌍의 최단거리를 구합니다.
7. 질의를 입력 받으면 하나씩 출력해줍니다.

시간복잡도

O(N³)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,d[251][251],i,j,k;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)d[i][j]=i==j?0:255;
    while(m--){
        cin>>i>>j>>k;
        if(k)d[i][j]=d[j][i]=0;
        else d[i][j]=0,d[j][i]=1;
    }
    for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    cin>>m;
    while(m--){
        cin>>i>>j;
        cout<<d[i][j]<<"\n";
    }
}