백준 28131 - K-지폐 (C++)

문제

• 문제 링크

  
   BOJ 28131 - K-지폐 
  

• 문제 요약

$N$개의 정점과 $M$개의 단방향 간선으로 이루어진 그래프가 주어진다.
정점 $S$에서 $T$까지 가려할 때, 이용료 합이 $K$의 배수이면서 최소가 되는 비용을 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10,000$

$1 ≤ M ≤ min(100,000, N*(N-1))$

$1 ≤ w ≤ 1000$

$1 ≤ K ≤ 50$

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)

풀이

우선 가중치 있는 유향 그래프에서 최단 거리를 찾아야 하므로 다익스트라를 떠올려볼 수 있다.
이제 어떻게 총 비용이 $K$의 배수가 되게 하냐가 문제인데..

알다시피 $S$부터 임의의 정점 $i$까지 도달하는 데엔 서로 다른 경로가 존재할 수 있다.
이 중 어떤 경로에서 드는 비용을 $Cost_i$라 하고, $mod$ $K$에 주목해보자.

구체적으로, $Dist[i][j]$를 "$Cost_i ≡ j$ $(mod$ $K)$일 때의 최소 비용" 으로 정의 하자는 것이다.
결국 답은 $Cost_T ≡ 0$ $(mod$ $K)$ 일 때 최소 비용을 묻고 있으니, $Dist[T][0]$을 보면 된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <pair<int, int>> Gr[10001];
int Dist[10001][51];
int n, m, k, s, t;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fill(&Dist[0][0], &Dist[10000][51], 1e9);
    cin >> n >> m >> k >> s >> t;
    for (int i, j, w; m--;)
        cin >> i >> j >> w, Gr[i].emplace_back(j, w);
}
void Solve()
{
    priority_queue <pair<int, int>> Q;
    for (Q.push({ Dist[s][0] = 0, s }); Q.size();)
    {
        auto [x, y](Q.top()); Q.pop();
        for (auto& [p, q] : Gr[y])
            if (int d(q - x); Dist[p][d % k] > d)
                Dist[p][d % k] = d, Q.push({ -d, p });
    }
    Dist[t][0] < 1e9 ? cout << Dist[t][0] : cout << "IMPOSSIBLE";
}
int main()
{
    Init();
    Solve();
}

comment

끝