[백준 24042번] 횡단보도

문제 링크: https://www.acmicpc.net/problem/24042

24042번: 횡단보도

<문제 풀이> 다익스트라 알고리즘

 

횡단보도를 건너기 위해 파란불이 켜지기를 기다려야 합니다. 이 대기 시간을 '가중치'라고 생각할 수 있습니다. 또한 횡단보도의 파란불은 주기를 가지고 있기 때문에, 이 문제에서는 각 간선이 여러 개의 가중치를 가질 수 있습니다.

 

A - B 간의 가중치는 i, M + i, 2M + i, 3M + i,... 와 같은 값을 가질 수 있습니다. 문제를 해결하기 위해, 다익스트라 알고리즘을 사용하여 다음 정점을 방문할 때 현재 가능한 가장 작은 가중치를 선택해 나가면 됩니다. 다익스트라 알고리즘을 사용하면서 모든 가능한 가중치를 미리  계산하여 삽입할 필요는 없습니다. 대신 문제에서 주어진 초기 가중치 i로부터 동적으로 값을 계산해나가야 합니다.

 

여기서 중요한 것은, A까지 도달했을 때의 시간보다 크면서 가장 작은 가중치를 선택해야 됩니다. 이를 위해 주기 M을 계속 더해서 가중치를 구하면 시간 초과가 발생합니다.

 

초기 가중치가 i일 때, 현재 시간을 t라고 가정하면, 초기 가중치 i에 M을 반복적으로 더하는 대신  M을 몇 번 더해야 할지를 계산하고 그 횟수를 M에 곱해서 초기 가중치 i에 더하면 O(1)에 가중치를 구할 수 있습니다.

 

이를 위해 현재 시간 t에서 초기 가중치 i를 빼고, 그 결과를 M으로 나누면, i에서 M을 몇 번 더해야 원하는 가중치를 얻을 수 있는지 바로 알 수 있습니다.

 

 

 

<C++소스코드>

 

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<cstring>
#include<functional>
#include<cmath>
using namespace std;


typedef long long ll;

const int MAX_N = 100000;
vector<pair<ll, int> > adj[MAX_N + 1];
ll d[MAX_N + 1];
int N, M;

ll dijkstra(int st) {
    memset(d, 0x3f, sizeof(d));
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    d[st] = 0;
    pq.push({ d[st], st });
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        ll cur_dist = cur.first;
        int cur_idx = cur.second;
        if (d[cur_idx] != cur_dist) continue;

        for (auto& nxt : adj[cur_idx]) {
            ll nxt_dist = nxt.first;
            int nxt_idx = nxt.second;
            if (cur_dist > nxt_dist) {
                nxt_dist += (ceil(((double)(cur_dist - nxt_dist)) / M)) * M;
            }
            if (d[nxt_idx] > nxt_dist) {
                d[nxt_idx] = nxt_dist;
                pq.push({ d[nxt_idx], nxt_idx });
            }
        }
    }
    return d[N];
}

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

    cin >> N >> M;
    for (ll i = 1; i <= M; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({ i, v });
        adj[v].push_back({ i, u });
    }

    cout << dijkstra(1);


    return 0;
}