| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1157680 | shn | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
// #include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 91;
struct node{
long long w , lim;
int to;
};
vector < node > g[N];
vector<long long> calculate_necessary_time(int n, int m, long long s, int q, vector<int> a, vector<int> b,vector<long long> l, vector<long long> c, vector<int> v,vector<int> u, vector<long long> t){
vector < long long > ans;
for(int i = 0; i < m; i++){
g[a[i]].pb({l[i] , c[i] , b[i]});
g[b[i]].pb({l[i] , c[i] , a[i]});
}
for(int i = 0; i < q; i++){
set < pair < pair < int , long long > , int > > st;
st.insert({{0 , t[i]} , v[i]});
pair < int , long long > dst[n];
for(int i = 0; i < n; i++) dst[i] = {n + 1 , n + 1};
dst[v[i]] = {0 , t[i]};
while(st.size()){
int v = st.begin() -> second;
st.erase(st.begin());
for(node it : g[v]){
int d = dst[v].first , tim = dst[v].second;
if(0 <= tim && tim <= it.lim - it.w){
tim += it.w;
}
else{
tim = it.w;
d++;
}
if(dst[it.to].first > d || dst[it.to].first == d && dst[it.to].second > tim){
st.erase({dst[it.to] , it.to});
dst[it.to] = {d , tim};
st.insert({dst[it.to] , it.to});
}
}
}
ans.pb(dst[u[i]].first * s + dst[u[i]].second - t[i]);
}
return ans;
}
int main(){
int n , m;
long long s;
int q;
cin >> n >> m >> s >> q;
vector < int > a , b;
vector < long long > l , c;
for(int i = 0; i < m; i++){
int x , y , z , t;
cin >> x >> y >> z >> t;
a.pb(x);
b.pb(y);
l.pb(z);
c.pb(t);
}
vector < int > v , u;
vector < long long > t;
for(int i = 0; i < q; i++){
int x , y , z;
cin >> x >> y >> z;
v.pb(x);
u.pb(y);
t.pb(z);
}
vector < long long > ans = calculate_necessary_time(n , m , s , q , a , b , l , c , v , u , t);
for(auto it : ans){
cout << it << '\n';
}
}