| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211559 | salmon | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
namespace{
const long long int inf = 1.1e18;
}
int N,M;
long long int S;
int Q;
vector<int> A,B;
vector<long long int> L,C;
long long int d[100][5100][100];
int main(){
vector<int> adjlst[100];
vector<vector<long long int>> ds[100];
vector<long long int> turns[100];
vector<long long int> turns1[100];
bool used[100];
int dit[100];
pair<long long int, long long int> adjmat[100][100];
scanf(" %d",&N);
scanf(" %d",&M);
scanf(" %d",&S);
scanf(" %d",&Q);
for(int i = 0; i < M; i++){
int h,h1;
long long int h2,h3;
scanf(" %d",&h);
scanf(" %d",&h1);
scanf(" %lld",&h2);
scanf(" %lld",&h3);
A.push_back(h);
B.push_back(h1);
L.push_back(h2);
C.push_back(h3);
}
for(int i = 0; i < M; i++){
A.push_back(B[i]);
B.push_back(A[i]);
L.push_back(L[i]);
C.push_back(C[i]);
}
for(int i = 0; i < M; i++){
adjlst[A[i]].push_back(i);
adjlst[B[i]].push_back(i + M);
}
for(int i = 0; i < N; i++){
for(int j : adjlst[i]) turns[i].push_back(C[j] - L[j]);
sort(turns[i].begin(),turns[i].end(), greater<int>());
turns[i].resize(unique(turns[i].begin(),turns[i].end()) - turns[i].begin() );
}
for(int i = 0; i < N; i++){
for(int j = 0; j < turns[i].size(); j++){
vector<long long int> temp = {};
for(int j = 0; j < N; j++){
temp.push_back(inf);
used[j] = false;
}
ds[i].push_back(temp);
ds[i][j][i] = turns[i][j];
for(int k = 0; k < N; k++){
pair<long long int, int> ii = {inf,-1};
for(int l = 0; l < N; l++) if(!used[l]) ii = min(ii,{ds[i][j][l],l });
if(ii.first == inf) break;
used[ii.second] = true;
int it = ii.second;
for(int l : adjlst[it]){
if(ii.first + L[l] <= C[l]) ds[i][j][B[l]] = min(ds[i][j][B[l]], ii.first + L[l]);
}
}
for(int k = 0; k < N; k++) printf("%d ",ds[i][j][k]);
printf("\n");
}
printf("\n");
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
adjmat[i][j] = {inf,inf};
}
}
for(int i = 0; i < N; i++){
long long int incre = turns[i][0];
long long int diff = inf;
//it 1
turns1[i].push_back(incre);
for(int j = 0; j < N; j++){
dit[j] = 0;
d[i][0][j] = ds[i][0][j];
}
for(int j = 0; j < N; j++){
if(d[i][0][j] == inf) continue;
while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][0][j]){
dit[j]++;
}
if(dit[j] == turns[j].size()) continue;
diff = min(diff,d[i][0][j] - turns[j][dit[j]] );
}
incre = incre - diff;
//it
for(int l = 1; l < M + 2; l++){
if(incre < 0) break;
turns1[i].push_back(incre);
vector<pair<int,int>> proc;
for(int j = 0; j < N; j++) d[i][l][j] = inf;
for(int j = 0; j < N; j++){
if(dit[j] == turns[j].size()) continue;
if(d[i][l - 1][j] - turns[j][dit[j]] != diff) continue;
for(int k = 0; k < N; k++){
if(d[i][l - 1][k] == inf && ds[j][dit[j]][k] == inf) d[i][l][k] = min(d[i][l][k], inf);
else d[i][l][k] = min(d[i][l][k], min(ds[j][dit[j]][k], d[i][l - 1][k] - diff));
}
dit[j]++;
}
diff = inf;
for(int j = 0; j < N; j++){
if(d[i][l][j] == inf) continue;
while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][l][j]){
dit[j]++;
}
if(dit[j] == turns[j].size()) continue;
diff = min(diff,d[i][l][j] - turns[j][dit[j]] );
}
if(incre - diff < 0) break;
incre = incre - diff;
}
int it = turns1[i].size() - 1;
for(int it = 0; it < turns1[i].size(); it++){
printf("f: ");
for(int j = 0; j < N; j++){
printf("%lld ",d[i][it][j]);
if(d[i][it][j] == inf) continue;
adjmat[i][j] = {1,d[i][it][j] - incre};
}
printf(" %d\n",incre);
}
printf("\n");
}
for(int k = 0; k < N; k++){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
adjmat[i][j] = min(adjmat[i][j],{adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second });
}
}
}
printf("\n");
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
printf("%lld ",adjmat[i][j].first);
}
printf("\n");
}
printf("\n");
vector<long long> ans;
for(int i = 0; i < Q; i++){
/*int u = U[i];
int v = V[i];
long long int h = T[i];*/
int u,v;
long long int h;
scanf(" %d",&u);
scanf(" %d",&v);
scanf(" %lld",&h);
long long int it = upper_bound(turns1[u].begin(),turns1[u].end(),h,greater<int>()) - turns1[u].begin() - 1;
if(d[u][it][v] != inf){
ans.push_back(d[u][it][v] - d[u][it][u]);
printf("%d %d %d\n",it,d[u][it][v],d[u][it][u]);
}
else{
pair<long long int,long long int> ii = {inf,inf};
for(int j = 0; j < N; j++){
if(d[u][it][j] != inf) ii = min(adjmat[j][v],ii);
}
printf("%lld\n",ii.first * S + ii.second - h);
ans.push_back(ii.first * S + ii.second - h);
}
}
for(long long int i : ans) printf("%d\n",i);
}