| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 908771 | 2024-01-16T20:05:45 Z | alexander707070 | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#define MAXN 107
using namespace std;
const long long inf=1e17;
struct edge{
int to;
long long l,c;
};
int n,m,qs,minv,from,to;
long long s,w,ans;
int a[MAXN],b[MAXN];
long long l[MAXN],c[MAXN];
long long dist[MAXN][MAXN],dst[MAXN];
vector<edge> v[MAXN];
int li[MAXN],tim;
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > q;
void dijkstra(int x){
for(int i=1;i<=n;i++){
dist[x][i]=inf;
}
dist[x][x]=0; tim++;
q.push({0,x});
while(!q.empty()){
minv=q.top().second;
q.pop();
if(li[minv]==tim)continue;
li[minv]=tim;
for(int i=0;i<v[minv].size();i++){
if(li[v[minv][i].to]==tim or dist[x][v[minv][i].to]<=dist[x][minv]+v[minv][i].l or dist[x][minv]>v[minv][i].c-v[minv][i].l)continue;
dist[x][v[minv][i].to]=dist[x][minv]+v[minv][i].l;
q.push({dist[x][v[minv][i].to],v[minv][i].to});
}
}
}
void query(int x,long long t){
for(int i=1;i<=n;i++){
dst[i]=inf;
}
dst[x]=t; tim++;
q.push({t,x});
while(!q.empty()){
minv=q.top().second;
q.pop();
if(li[minv]==tim)continue;
li[minv]=tim;
for(int i=0;i<v[minv].size();i++){
if(li[v[minv][i].to]==tim or dst[v[minv][i].to]<=dst[minv]+v[minv][i].l or dst[minv]>v[minv][i].c-v[minv][i].l)continue;
dst[v[minv][i].to]=dst[minv]+v[minv][i].l;
q.push({dst[v[minv][i].to],v[minv][i].to});
}
}
}
bool u[MAXN][MAXN][MAXN];
long long dp[MAXN][MAXN][MAXN];
long long ff(int x,int y,int day){
if(x==y)return 0;
if(day>n)return inf;
if(u[x][y][day])return dp[x][y][day];
u[x][y][day]=true;
dp[x][y][day]=inf;
for(int p=1;p<=n;p++){
if(dist[x][p]!=inf){
if(p!=y){
dp[x][y][day]=min(dp[x][y][day],ff(p,y,day+1)+s);
}else{
dp[x][y][day]=min(dp[x][y][day],ff(p,y,day+1)+dist[x][y]);
}
}
}
return dp[x][y][day];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>s>>qs;
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i]>>l[i]>>c[i];
a[i]++; b[i]++;
v[a[i]].push_back({b[i],l[i],c[i]});
v[b[i]].push_back({a[i],l[i],c[i]});
}
for(int i=1;i<=n;i++){
dijkstra(i);
}
for(int i=1;i<=qs;i++){
cin>>from>>to>>w;
from++; to++;
query(from,w); ans=inf;
for(int f=1;f<=n;f++){
if(dst[f]!=inf){
if(f!=to)ans=min(ans,s+ff(f,to,0));
else ans=min(ans,dst[to]);
}
}
cout<<ans-w<<"\n";
}
return 0;
}