11562 백양로 브레이크

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

플로이드를 돌려서 어찌어찌 해야할 것 같다. 약간의 트릭을 주면 된다. u,v,b를 받아서 양방향 간선이면 d[u][v]=d[v][u]=0, 단방향 간선이면 d[u][v]=0,d[v][u]=1로 줘서 양방향 간선으로 만들어 준다. 그리고 플로이드를 돌리면 모든 정점 사이에 대해서 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 하는지 알 수 있다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int n,m,u,v,b,k,s,e,i,j,d[300][300];
 
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=i==j?0:INF;
    while(m--) scanf("%d %d %d",&u,&v,&b),d[u][v]=0,d[v][u]=b?0: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]);
    scanf("%d",&k);
    while(k--) scanf("%d %d",&s,&e),printf("%d\n",d[s][e]);
    return 0;
}