백준 30869 - 빨리 기다리기 (C++)

문제

• 문제 링크

  
   BOJ 30869 - 빨리 기다리기 
  

• 문제 요약

$N$개의 버스 정류장에 대해 $M$개의 버스 노선 정보가 주어진다.
'빨리 기다리기'를 최대 $K$번까지 사용할 수 있을 때, $1$번 정류장에서 $N$번 정류장까지 가는 데에 걸리는 최소 시간을 구해보자.

• 제한

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




$2 ≤ N ≤ 500$

$0 ≤ K ≤ 500$

$1 ≤ M ≤ 250,000$

$1 ≤ t_i, g_i ≤ 10,000$

알고리즘 분류

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

풀이

그래프에서 두 정점쌍 간의 최단 거리는 기본적으로 다익스트라를 이용해 쉽게 구할 수 있다.
그런데 이번 문제에선, 고려해야 할 것들이 조금 있다.

간선마다 배차 간격이 존재한다.

최대 $K$번까지 '빨리 기다리기'를 사용해 배차 간격을 무시할 수 있다.

정점 $now$까지 $cost$의 시간이 걸렸고 $cnt$번의 '빨리 기다리기'를 사용했다고 해보자. 동시에 정점 $nxt$를 향하는 가중치 $weight$, 배차 간격 $g$인 간선을 보고 있다고 해보자.

문제 정의에 따라 이 순간 취할 수 있는 행동은 다음과 같을 것이다.

• $cost$가 $g$로 나누어 떨어질 때
  • 이 때는 배차 간격을 신경 쓸 필요 없이, 바로 출발할 수 있다. 소요 시간은 $cost + weight$.
• $cost$가 $g$로 나누어 떨어지지 않을 때
  • $cnt < k$ 라면, '빨리 기다리기'를 사용해 $nxt$로 이동할 수 있다. 이 역시 소요 시간은 $cost + weight$.
  • 배차가 될 때까지 기다렸다가 $nxt$로 이동한다. $cost + weight$에 기다린 시간을 보정한 값이 소요 시간이다.

---

이제 거리 테이블을 다음과 같이 정의하고, 위 내용대로 다익을 돌려주면 된다.

$dist[x][y]$ : $1$번 정점에서 '빨리 기다리기'를 $y$번 사용하여 $x$번 정점에 도착하는 데에 걸리는 최소 시간.

+ 왜자꾸 틀리나 봤더니.. 간선을 양방향으로 추가해놓고 있었다.

요새 죙일 학교 졸작 하느라 정신이 살짝 나간 건가?

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
 
    vector <tuple <int, int, int>> Gr[501];
    while (m--)
    {
        int s, e, t, g; cin >> s >> e >> t >> g;
        Gr[s].emplace_back(e, t, g);
    }
 
    priority_queue <tuple <int, int, int>> pq;
    vector <vector <int>> dist(501, vector <int>(501, 2e9));
 
    for (pq.push({ dist[1][0] = 0, 1, 0 }); pq.size();)
    {
        auto [cost, now, cnt](pq.top()); pq.pop();
        if (dist[now][cnt] < (cost *= -1))
            continue;
 
        for (auto& [nxt, weight, g] : Gr[now])
        {
            int cur(cost + weight);
            if (!(cost % g))
            {
                if (dist[nxt][cnt] > cur)
                    pq.push({ -(dist[nxt][cnt] = cur), nxt, cnt });
            }
            else
            {
                if (cnt < k && dist[nxt][cnt + 1] > cur)
                    pq.push({ -(dist[nxt][cnt + 1] = cur), nxt, cnt + 1 });
 
                cur = cost / g * g + g + weight;
                if (dist[nxt][cnt] > cur)
                    pq.push({ -(dist[nxt][cnt] = cur), nxt, cnt });
            }
        }
    }
 
    int ans(*min_element(dist[n].begin(), dist[n].end()));
    cout << (ans < 2e9 ? ans : -1);
}

comment

끝