
플래는 될줄 알았는데
웰노운이라서 골드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;
}

반응형