| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1209418 | salmon | Escape Route (JOI21_escape_route) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int N;
int M;
long long int S;
int Q;
vector<int> adjlst[100];
int A[100],B[100];
long long L[100],C[100];
long long int d[100][5100][100];
vector<long long int> t[100];
bool done[100];
int limit[5100];
pair<long long int, long long int> adjmat[100][100];
pair<long long int, long long int> adjmat1[100][5100][100];
long long int inf = 1.1e18;
int main(){
scanf(" %d",&N);
scanf(" %d",&M);
scanf(" %lld",&S);
scanf(" %d",&Q);
for(int i = 0; i < M; i++){
scanf(" %d",&A[i]);
scanf(" %d",&B[i]);
scanf(" %lld",&L[i]);
scanf(" %lld",&C[i]);
adjlst[A[i]].push_back(i);
adjlst[B[i]].push_back(i);
}
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 = 0;
long long int nextincre = 0;
for(int l = 0; l < M; l++){
for(int j = 0; j < N; j++){
d[i][l][j] = inf;
limit[i] = inf;
done[j] = false;
}
d[i][l][i] = incre;
t[i].push_back(incre);
nextincre = inf;
for(int k = 0; k < N; k++){
pair<long long int,int> chose = {inf, -1};
for(int j = 0; j < N; j++) if(!done[j]) chose = min( {d[i][l][j],j}, chose);
if(chose.first == inf) break;
int it = chose.second;
nextincre = min(nextincre, limit[it] + incre);
done[it] = true;
for(int j : adjlst[it]){
if(chose.first + L[j] <= C[j]){
if(A[j] == it && d[i][l][B[j]] > chose.first + L[j] ){
limit[B[j]] = C[j] - (chose.first + L[j]) + 1;
d[i][l][B[j]] = chose.first + L[j];
}
else if(d[i][l][A[j]] > chose.first + L[j]){
limit[A[j]] = C[j] - (chose.first + L[j]) + 1;
d[i][l][A[j]] = chose.first + L[j];
}
}
}
}
if(nextincre == inf) break;
incre = nextincre;
}
for(int j = 0; j < N; j++){
if(d[i][0][j] != inf) adjmat[i][j] = {1,d[i][0][j]};
}
}
for(int k = 0; k < N; k++){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(adjmat[i][k].first != inf && adjmat[k][j].first != inf){
adjmat[i][j] = min(adjmat[i][j], {adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second } );
}
}
}
}
/*
for(int i = 0; i < N; i++){
for(int j = 0; j < t[i].size(); j++){
for(int k = 0; k < N; k++){
}
for(int k = 0; k < N; k++){
}
}
}*/
for(int i = 0; i < Q; i++){
int u,v;
long long int h;
scanf(" %d",&u);
scanf(" %d",&v);
scanf(" %lld",&h);
//for(int k : t[u]) printf("%d ",k);
//printf("\n");
int it = upper_bound(t[u].begin(),t[u].end(),h) - t[u].begin() - 1;
//printf("i: %d\n",it);
if(d[u][it][v] != inf){
printf("%lld\n",d[u][it][v] - t[u][it]);
continue;
}
pair<long long int,long long int> ii = {N + 5, inf};
for(int j = 0; j < N; j++){
if(d[u][it][j] != inf){
ii = min(ii,adjmat[j][v]);
}
}
printf("%lld\n",ii.first * S + ii.second - h);
}
}