Koder / 박성훈
article thumbnail

플래는 될줄 알았는데

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

세상 말세다 정말 엉엉엉

 

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

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

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

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

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을 사용해주도록 하자.

 

소스코드 펼쳐보기

더보기
#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;
}

 

 

반응형