| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 907440 | lighton | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct Edge{
int to;
ll t,c;
};
int N,M;
int S,Q;
vector<Edge> adj[101];
ll inf =1e18;
ll d[101];
ll dijk(int st ,int en , ll t){
forf(i,0,N) d[i] = inf;
d[st] = t;
priority_queue<pair<ll,int> > pq;
pq.push({-t,st});
while(pq.size()){
int now = pq.top().second;
ll nowt = -pq.top().first;
pq.pop();
if(d[now] < nowt) continue;
for(auto &edge : adj[now]){
ll newt;
if(nowt%S + edge.t <= edge.c) newt = nowt+edge.t;
else newt = S*((nowt/S)+1)+edge.t;
if(newt < d[edge.to]){
d[edge.to] = newt;
pq.push({-newt,edge.to});
}
}
}
return d[en]-t;
}
int main(){
scanf("%d %d %d %d" , &N,&M,&S,&Q);
forf(i,1,M){
int u,v; ll t,c;
scanf("%d %d %lld %lld" , &u,&v,&t,&c);
adj[u].push_back({v,t,c});
adj[v].push_back({u,t,c});
}
while(Q--){
int u,v; ll t;
scanf("%d %d %lld" , &u,&v,&t);
printf("%lld\n" , dijk(u,v,t));
}
}