Submission #908771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
908771	2024-01-16T20:05:45 Z	alexander707070	Escape Route (JOI21_escape_route)	C++17	Compilation error	0 ms	0 KB

escape_route

#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;
}
 

Compilation message

escape_route.cpp: In function 'void dijkstra(int)':
escape_route.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'void query(int, long long int)':
escape_route.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccCfACys.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCCzPou.o:escape_route.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccCfACys.o: in function `main':
grader.cpp:(.text.startup+0x6ea): undefined reference to `calculate_necessary_time(int, int, long long, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >, std::vector<long long, std::allocator<long long> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >)'
collect2: error: ld returned 1 exit status