#include<bits/stdc++.h>
#include "escape_route.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;
vector<long long> sol;
int a[10007],b[10007];
long long l[10007],c[10007];
long long dist[MAXN][MAXN],dst[MAXN];
int parent[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;
parent[i]=-1;
}
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;
parent[v[minv][i].to]=minv;
q.push({dst[v[minv][i].to],v[minv][i].to});
}
}
}
vector< pair<long long,vector<int> > > dists[MAXN];
void findchanges(int x,long long l,long long r,vector<int> ls,vector<int> rs){
if(l+1==r){
dists[x].push_back({l,ls});
return;
}
long long mid=(l+r)/2;
query(x,mid);
vector<int> curr={};
for(int i=1;i<=n;i++){
curr.push_back(parent[i]);
}
if(ls!=curr){
findchanges(x,l,mid,ls,curr);
}
if(curr!=rs){
findchanges(x,mid,r,curr,rs);
}
}
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];
}
long long path(int x){
if(parent[x]==-1 or li[x]==tim)return dst[x];
li[x]=tim;
for(int i=0;i<v[x].size();i++){
if(v[x][i].to==parent[x]){
dst[x]=path(v[x][i].to)+v[x][i].l;
}
}
return dst[x];
}
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> U,vector<int> V, vector<long long> T){
n=N; m=M; s=S; qs=Q;
//cin>>n>>m>>s>>qs;
for(int i=1;i<=m;i++){
a[i]=A[i-1]; b[i]=B[i-1]; l[i]=L[i-1]; c[i]=C[i-1];
//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<=n;i++){
vector<int> ll,rr;
query(i,0);
for(int f=1;f<=n;f++){
ll.push_back(parent[f]);
}
query(i,s);
for(int f=1;f<=n;f++){
rr.push_back(parent[f]);
}
findchanges(i,0,s,ll,rr);
dists[i].push_back({s,rr});
}
for(int i=1;i<=qs;i++){
from=U[i-1]; to=V[i-1]; w=T[i-1];
//cin>>from>>to>>w;
from++; to++;
int lt=-1,rt=dists[from].size(),mid;
while(lt+1<rt){
mid=(lt+rt)/2;
if(w<=dists[from][mid].first){
rt=mid;
}else{
lt=mid;
}
}
lt=rt;
/*
for(int f=1;f<=n;f++){
dst[f]=inf;
parent[f]=dists[from][lt].second[f-1];
}
dst[from]=w;
tim++; ans=inf;
for(int f=1;f<=n;f++){
if(path(f)!=inf){
if(f!=to)ans=min(ans,s+ff(f,to,0));
else ans=min(ans,path(f));
}
}
*/
sol.push_back(ans-w);
}
return sol;
}
/*
int main(){
calculate_necessary_time();
}
*/
Compilation message
escape_route.cpp: In function 'void dijkstra(int)':
escape_route.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i=0;i<v[minv].size();i++){
| ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'void query(int, long long int)':
escape_route.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<v[minv].size();i++){
| ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'long long int path(int)':
escape_route.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4702 ms |
117820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
