[BOJ/백준][Gold4] 11562 : 백양로 브레이크 (C++)

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

11562번: 백양로 브레이크

 

[난이도] Gold4
[유형] 다익스트라, 플로이드 워셜

[풀이]
원래 길이 있는 경우에는 비용이 안드므로 0의 cost,
단방향 통행만 가능하면 그 반대로 오는길은 1의 cost를 준 뒤
다익스트라를 돌려주면 몇개의 단방향 길을 바꿔야 하는지 알 수 있다.
모든 쿼리마다 다익스트라를 돌리면 시간초과가 나므로 출발점 N개에 대해
한번씩만 호출되도록 한다.

(플로이드 워셜로 풀면 훨씬 간결하게 풀 수 있다.)

 

#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
int N,M,K,inf=9e8;
vector<pair<int,int>> adj[251];
int s,e,dist[251][251];
void dijk(){
    fill(dist[s],dist[s]+N+1,inf);
    priority_queue<pair<int,int>> pq;
    dist[s][s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        int cur = qt.second, cd=-qt.first;
        if(cd > dist[s][cur]) continue;
        for(auto next : adj[cur]){
            int nxt = next.first, nd = cd+next.second;
            if(dist[s][nxt] > nd){
                dist[s][nxt] = nd;
                pq.push({-nd,nxt});
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        adj[u].push_back({v,0});
        adj[v].push_back({u,!k});
    }
    scanf("%d",&K);
    memset(dist,-1,sizeof(dist));
    while(K--){
        scanf("%d%d",&s,&e);
        if(dist[s][s]==-1) dijk();
        printf("%d\n",dist[s][e]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11562.cpp