Submission #1159578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159578		PagodePaiva	Escape Route (JOI21_escape_route)	C++20	Compilation error	0 ms	0 KiB

escape_route

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 41;
const int inf = 1e16;
int n, m, s, q;
int dp[N][N];
vector <array <int, 3>> g[N];
int dist[N];
int last[N];

void solve(int st){
    dp[st][st] = 0;
    for(int i = 0;i < n;i++){
        dist[i] = inf;
    }
    dist[st] = 0;
    priority_queue <pair <int, int>> pq;
    pq.push({0, st});
    while(!pq.empty()){
        auto [tempo, v] = pq.top();
        pq.pop();
        tempo *= -1;
        if(tempo != dist[v]) continue;
        for(auto [x, l, c] : g[v]){
            if(dist[v]+l > c) continue;
            if(dist[v]+l < dist[x]){
                dist[x] = dist[v]+l;
                dp[st][x] = dist[x];
                pq.push({-dist[x], x});
            }
        }
    }
    return;
}

pair <int, int> dist2[N];

void solve2(int u, int v, int t){
    set <int> vertices;
    for(int i = 0;i < n;i++){
        dist[i] = inf;
    }
    dist[u] = t;
    priority_queue <pair <int, int>> pq;
    pq.push({-t, u});
    while(!pq.empty()){
        auto [tempo, v] = pq.top();
        pq.pop();
        tempo *= -1;
        if(tempo != dist[v]) continue;
        vertices.insert(v);
        for(auto [x, l, c] : g[v]){
            if(dist[v]+l > c) continue;
            if(dist[v]+l < dist[x]){
                dist[x] = dist[v]+l;
                pq.push({-dist[x], x});
            }
        }
    }
    for(int i = 0;i < n;i++){
        dist2[i] = {90, inf};
    }
    for(auto i : vertices){
        dist2[i] = {0, dist[i]};
        pq.push({-s*dist2[i].first-dist2[i].second, i});
    }
    while(!pq.empty()){
        auto [d, v] = pq.top();
        pq.pop();
        d *= -1;
        //cout << d << ' ' << v << '\n';
        if(d != dist2[v].first*s+dist2[v].second) continue;
        for(int i = 0;i < n;i++){
            if(dp[v][i] > -1){
                if((dist2[v].first+1)*s+dp[v][i] < dist2[i].first*s+dist2[i].second){
                    dist2[i] = make_pair(dist2[v].first+1, dp[v][i]);
                    pq.push({-s*dist2[i].first-dist2[i].second, i});
                }
            }
        }
    }
    cout << dist2[v].first*s+dist2[v].second-t << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> m >> s >> q;    
    for(int i = 0;i < m;i++){
        int a, b, l, c;
        cin >> a >> b >> l >> c;
        g[a].push_back({b, l, c});
        g[b].push_back({a, l, c});
    }
    for(int i = 0;i < n;i++){
        solve(i);
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
    while(q--){
        int u, v, t;
        cin >> u >> v >> t;
        solve2(u, v, t);
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccfi0IQI.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3oR1RH.o:escape_route.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccfi0IQI.o: in function `main':
grader.cpp:(.text.startup+0x6e0): 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