백준 BOJ 24042 - 횡단보도

플래는 될줄 알았는데

웰노운이라서 골드1이란다 ㅠㅠ

세상 말세다 정말 엉엉엉

 

다익스트라 문제인데 그래프 가중치를 시간으로 생각해주면 된다.

저장된 최단거리가 최단시간에 도착하였을 경우의 시간이 되는 셈.

횡단보도 불이 들어올때까지 기다릴 수 있기 때문에,

당장은 가지 못하는 도로이더라도 처리를 해줘야 한다.

      

      

      

    
    

      <cpp />
    
while(dist >= ndist) ndist += M;
if(dist > ndist)ndist += (ll)ceil((double)(dist-ndist)/M)*M;

아이디어는 대략 위와 같은데,

처음 K초에 지날수 있게 되는 다리는

K+M초, K+2M초, K+3M초 등등.... 에 다시 지날수 있게 되므로

첫번째 줄에서 M을 하나씩 더해가며 계산했지만 시간초과를 받았다.

 

그렇기때문에 둘 사이의 시간을 빼고 M으로 나눈 뒤, 올림함수를 적용해주고 다시 M을 곱하는 방법으로

dist에 가장 가까우면서도 dist보다는 큰 ndist를 구해낼 수 있다.

이렇게 구해낸 시간을 기준으로 다익스트라를 돌려주면 AC.

 

범위가 int범위를 넘어가는듯하니 long long을 사용해주도록 하자.

 

소스코드 펼쳐보기

      

      

      

    
    

      <cpp />
    
#include <bits/stdc++.h>
#define INF 998244353998244353LL
using namespace std;
typedef long long ll;

priority_queue<pair<ll,int>> pq;
vector<pair<int,int>> g[123456];

ll d[123456] = {0};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N,M,a,b;
	cin >> N >> M;
	
	for(int i=1; i<=M; i++){
		cin >> a >> b;
		g[a].push_back({b,i});
		g[b].push_back({a,i});
	}
	
	for(int i=0; i<123456; i++) d[i] = INF;
	pq.push({0,1});
	d[1] = 0;
	
	while(!pq.empty()){
		int node =  pq.top().second;
		ll  dist = -pq.top().first;
		pq.pop();
		
		if(d[node] < dist) continue;
		
		for(auto nxt : g[node]){
			int nnode = nxt.first;
			ll  ndist = nxt.second;
			
			//while(dist >= ndist) ndist += M;
			if(dist > ndist)ndist += (ll)ceil((double)(dist-ndist)/M)*M;
			
			if(d[nnode] > ndist){
				d[nnode] = ndist;
				pq.push({-ndist, nnode});
			}
		}
	}
	
	//for(int i=1; i<=N; i++){ printf("%d ", d[i]); }
	cout << d[N];
	return 0;
}