| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1159578 | PagodePaiva | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 41;
const int inf = 1e16;
int n, m, s, q;
int dp[N][N];
vector <array <int, 3>> g[N];
int dist[N];
int last[N];
void solve(int st){
dp[st][st] = 0;
for(int i = 0;i < n;i++){
dist[i] = inf;
}
dist[st] = 0;
priority_queue <pair <int, int>> pq;
pq.push({0, st});
while(!pq.empty()){
auto [tempo, v] = pq.top();
pq.pop();
tempo *= -1;
if(tempo != dist[v]) continue;
for(auto [x, l, c] : g[v]){
if(dist[v]+l > c) continue;
if(dist[v]+l < dist[x]){
dist[x] = dist[v]+l;
dp[st][x] = dist[x];
pq.push({-dist[x], x});
}
}
}
return;
}
pair <int, int> dist2[N];
void solve2(int u, int v, int t){
set <int> vertices;
for(int i = 0;i < n;i++){
dist[i] = inf;
}
dist[u] = t;
priority_queue <pair <int, int>> pq;
pq.push({-t, u});
while(!pq.empty()){
auto [tempo, v] = pq.top();
pq.pop();
tempo *= -1;
if(tempo != dist[v]) continue;
vertices.insert(v);
for(auto [x, l, c] : g[v]){
if(dist[v]+l > c) continue;
if(dist[v]+l < dist[x]){
dist[x] = dist[v]+l;
pq.push({-dist[x], x});
}
}
}
for(int i = 0;i < n;i++){
dist2[i] = {90, inf};
}
for(auto i : vertices){
dist2[i] = {0, dist[i]};
pq.push({-s*dist2[i].first-dist2[i].second, i});
}
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
d *= -1;
//cout << d << ' ' << v << '\n';
if(d != dist2[v].first*s+dist2[v].second) continue;
for(int i = 0;i < n;i++){
if(dp[v][i] > -1){
if((dist2[v].first+1)*s+dp[v][i] < dist2[i].first*s+dist2[i].second){
dist2[i] = make_pair(dist2[v].first+1, dp[v][i]);
pq.push({-s*dist2[i].first-dist2[i].second, i});
}
}
}
}
cout << dist2[v].first*s+dist2[v].second-t << '\n';
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> n >> m >> s >> q;
for(int i = 0;i < m;i++){
int a, b, l, c;
cin >> a >> b >> l >> c;
g[a].push_back({b, l, c});
g[b].push_back({a, l, c});
}
for(int i = 0;i < n;i++){
solve(i);
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
cout << dp[i][j] << ' ';
}
cout << '\n';
}
while(q--){
int u, v, t;
cin >> u >> v >> t;
solve2(u, v, t);
}
}