📝 문제 정보#
🧐 관찰 및 접근#
- 시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자.
- $KX$초 단위로 출구가 도는게 로테이션 돌고, 이분탐색으로 그 타이밍을 찾은 후 그 블럭에서 나갈 수 있는지, 그 다음블럭에서 나갈 수 있는지 체크하면 될 것 같다.
💻 풀이#
- 코드 (C++):
void solve(){
ll N, M, K; cin >> N >> M >> K;
vector<vector<pll>> links(N+1);
rep(i, 0, M){
ll u, v, w; cin >> u >> v >> w;
links[u].push_back({v, w});
links[v].push_back({u, w});
}
vector<ll> dist(N+1, LLONG_MAX);
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[1] = 0;
pq.push({0, 1});
while(!pq.empty()){
auto [cd, cur] = pq.top(); pq.pop();
if(dist[cur] < cd) continue;
for(auto [nxt, w]: links[cur]){
ll nd = cd + w;
if(nd < dist[nxt]){
dist[nxt] = nd;
pq.push({nd, nxt});
}
}
}