백준 24042 - 횡단보도(C++)

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

24042번: 횡단보도

1번에서 N번 정점까지 횡단보도를 통해 이동할 때 최소 이동 시간을 구하는 문제입니다.

문제에서 주의할 점은 횡단보도가 한번에 바뀌는 것이 아닌, 번호 순서대로 바뀐다는 점입니다.
1번 -> 2번 -> ……… -> M번 횡단보도 순으로 바뀝니다.

여기서 생각해봐야 할 점이 5번 도로를 지났다고 했을 때, 7번 도로를 건넌다고 한다면 2분을 기다린 후 건너면 됩니다.
그렇다면 5번 도로를 건넌 뒤, 1번 도로를 건너려고 한다면, 얼마나 기다려야 되는지 입니다.

이때는 M번 도로까지 전부 바뀐 뒤, 다시 1번 도로가 바뀔 때까지 기다려야 됩니다.
그렇다면, 이때 1번 도로를 건넌 시간은 M + 1분이 될 것입니다.

여기서 알 수 있는 것은 현재 도로 번호 보다 큰 도로로 가는 것은 새로운 주기를 거칠 필요가 없습니다.
하지만, 자신보다 번호가 작은 도로를 건너려고 한다면, 다음 주기가 될 때까지 기다려야 됩니다.

이를 구현하기 위해서 도로를 저장할 때 1번부터 M번 도로까지 지정을 해준 뒤, 다익스트라 탐색 중에서
도로 번호 비교를 통해 다음 주기인지 아닌지를 확인 후, 값을 구해주면 됩니다.

마지막으로 값이 int 범위를 넘기에 계산에 사용된 변수는 모두 long long 형으로 만들어 줘야 합니다.

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

long long N, M;
vector<pair<int, long long>> connect[100001];
priority_queue<pair<pair<long long, long long>, pair<int, int>>> q; // 시간, 주기, 도로 번호, 정점
long long Distance[100001];

void reset_distance(){
	for(int i = 1; i <= N; i++){
		Distance[i] = INF;
	}
}

void Dijstra(){
	q.push({{-0, 0}, {0, 1}});
	Distance[1] = 0;
	while(!q.empty()){
		int x = q.top().S.S;
		int num = q.top().S.F; // 현재 몇번째 도로인지
		long long T = q.top().F.S; // 몇번째 주기인지
		long long cost = -q.top().F.F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			long long n_cost = 0;
			if(num > connect[x][i].S){  // 다음에 갈 도로의 번호가 작을 때는 다음 주기로 갈 수 있다.
				n_cost = connect[x][i].S + M * (T + 1); 
				if(Distance[xx] > n_cost){
					Distance[xx] = n_cost;
					q.push({{-Distance[xx], T+1}, {connect[x][i].S, xx}});
				}
			}
			else{ // 다음에 갈 도로의 번호가 클 때는 현재 주기로 갈 수 있다.
				n_cost = connect[x][i].S + M * T; 
				if(Distance[xx] > n_cost){
					Distance[xx] = n_cost;
					q.push({{-Distance[xx], T}, {connect[x][i].S, xx}});
				}
			}
		}
	}
}

void solve(){
	reset_distance();
	Dijstra();	
	cout << Distance[N];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y;
		cin >> x >> y;
		connect[x].push_back({y, i});
		connect[y].push_back({x, i});
	}	
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.