백준 1238 파티

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

1238번: 파티

이 문제는 다익스트라와 역방향 그래프의 응용법? 사용법?을 한 가지 더 익힐 수 있는 좋은 문제다.

그리고 이 문제는 플로이드와샬을 사용하기는 힘들다 -> O(n^3)이기 때문이다.

위의 그림을 보자. 보통 다익스트라 최단경로 문제에서는 1번에서 출발하여 6번까지 가려고 할 때 소모되는 비용이나 경로를 출력하라고 한다. 그러면 보통 1번 정점에서 시작하여 우선순위 큐를 통해 그래프 전체를 확인하고 마무리한다. 그런 후에 6번 정점에 담긴 비용을 확인하여 답을 구한다. 여기서 우리는 사실 1번에서 6번까지 가는 최단경로만 구한 게 아니라, 1번에서 출발하여 다른 모든 정점에 대한 최단경로를 구한 것이다. 단지 그중에 6번 도착점 값만 확인했을 뿐이었다. 

여기서 중요한 것은 출발점이 주어지면 그래프내의 모든 정점에 대한 최단경로가 단 한 번의 다익스트라 연산을 통해 구해진다는 점이다.

 

이 문제에서는 출발점이 아니라 도착점이 주어진다. 모든 정점에서 그 도착점에 다다르기 위한 최단경로를 구해야 한다. 그렇다면 모든 정점에서 매번 다익스트라를 돌려야 할까? 벌써 뭔가 직관적으로 그게 함정이라는 느낌이 온다.

여기서 역방향 그래프가 등장한다!

위의 그래프는 원래 그래프에서 간선만 반대방향으로 뒤집은 것이다. 이제 아까는 도착점이었던 6번을 출발점으로 삼는다. 그렇게 하고 다익스트라를 단 한 번만 돌린다. 생각을 조금 더 해본다면 느낌이 올 것이다! 간선 방향을 뒤집어서 최단경로를 구했지만, 원래 그래프에서도 각 정점이 6번 도착점에 오기 위해서는 같은 경로를 선택해야 한다는 것을. 이렇게 역방향 그래프를 사용하면, 단 한번의 다익스트라 연산을 통해 각 정점에서 6번 도착점에 이르기 위한 최단경로 비용을 모두 구할 수 있다.

 

처음에 입력받을 때, 역방향 그래프도 같이 만들어주면 된다.

 

<주요 내용>

다익스트라, 역방향 그래프

 

<코드>

C++

아래에서 pq1과 pq2는 하나로 공용해도 된다.

#include <iostream>
#include<vector>
#include<queue>
#define endl '\n'
using namespace std;
const int stNum=1000+1;
const int big=(1000-1)*100+1;
vector<vector<pair<int,int>>> g1(stNum);
vector<vector<pair<int,int>>> g2(stNum);
int costs1[stNum],costs2[stNum];
struct cmp1
{
    int operator()(const int &a, const int &b)
    {
        return costs1[a] > costs1[b];
    }
};
struct cmp2
{
    int operator()(const int &a, const int &b)
    {
        return costs2[a] > costs2[b];
    }
};
priority_queue<int,vector<int>,cmp1> pq1;
priority_queue<int,vector<int>,cmp2> pq2;
int n,m,x,a,b,w,qs,start;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m>>x;
    while(m--){
        cin>>a>>b>>w;
        g1[a].emplace_back(make_pair(b,w));
        g2[b].emplace_back(make_pair(a,w));
    }

    fill(costs2,costs2+n+1,big);
    costs2[x]=0;
    pq2.emplace(x);
    while(pq2.size()){
        qs=pq2.size();
        while(qs--){
            int start=pq2.top();
            pq2.pop();
            for(auto &p:g2[start]){
                int& sCost=costs2[start];
                int& dCost=costs2[p.first];
                if(sCost+p.second<dCost){
                    pq2.emplace(p.first);
                    dCost=sCost+p.second;
                }
            }
        }
    }

    fill(costs1,costs1+n+1,big);
    costs1[x]=0;
    pq1.emplace(x);
    while(pq1.size()){
        qs=pq1.size();
        while(qs--){
            int start=pq1.top();
            pq1.pop();
            for(auto &p:g1[start]){
                int& sCost=costs1[start];
                int& dCost=costs1[p.first];
                if(sCost+p.second<dCost){
                    pq1.emplace(p.first);
                    dCost=sCost+p.second;
                }
            }
        }
    }

    int mx=0;
    for(int i=1;i<n+1;i++){
        mx=max(mx,costs1[i]+costs2[i]);
    }
    cout<<mx;
    return 0;
}

 

파이썬

C++코드와 마찬가지로, 비용 배열을 2개 만들고, 2번의 다익스트라를 통해 각각 채운 다음

이후 합산해주는 방식이다.

import sys
import heapq
si = sys.stdin.readline

n, m, x = [int(e) for e in si().split()]
big = int(1e2)*int(1e3)+1
g, ig = [[]for _ in range(n+1)], [[]for _ in range(n+1)]
cost1, cost2 = [big for _ in range(n+1)], [big for _ in range(n+1)]
cost1[x], cost2[x] = 0, 0
for _ in range(m):
    a, b, c = [int(e) for e in si().split()]
    g[a].append((b, c))
    ig[b].append((a, c))

pq = []
heapq.heappush(pq, (0, x))
while pq:
    c, curr = heapq.heappop(pq)
    if cost1[curr] < c:
        continue
    for np in g[curr]:
        if cost1[np[0]] > c+np[1]:
            cost1[np[0]] = c+np[1]
            heapq.heappush(pq, (cost1[np[0]], np[0]))
heapq.heappush(pq, (0, x))
while pq:
    c, curr = heapq.heappop(pq)
    if cost2[curr] < c:
        continue
    for np in ig[curr]:
        if cost2[np[0]] > c+np[1]:
            cost2[np[0]] = c+np[1]
            heapq.heappush(pq, (cost2[np[0]], np[0]))

for i in range(1, n+1):
    cost1[i] += cost2[i]

cost1[0] = 0
print(max(cost1))