oj.uz

Submission #973211

# Submission time Handle Problem Language Result Execution time Memory
973211 2024-05-01T16:05:17 Z shezitt Commuter Pass (JOI18_commuter_pass) C++14
24 / 100
 46 ms 4948 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>

using namespace std;

using ll = long long;

#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second

const int MAXN = 1010;

vector<ii> adj[MAXN];

int n, m, s, t, u, v;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;


    fore(i, 0, m){
        int x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }

    auto dijkstra = [&](int r, vi &dis) -> void {
        dis[r] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push({0, r});
        while(sz(pq)){
            auto [cost, node] = pq.top();
            pq.pop();

            if(cost != dis[node]) continue;

            for(auto [to, c] : adj[node]){
                if(dis[node] + c < dis[to]){
                    dis[to] = dis[node] + c;
                    pq.push({dis[to], to});
                }
            }

        }
    };

    vector<vi> d(n+1, vi(n+1, 4e18));

    auto dijkstraDag = [&](int r, vi &dis) -> vector<vi> {
        vector<vi> parent(n+1);
        dis[r] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push({0, r});

        while(sz(pq)){
            auto [cost, node] = pq.top(); pq.pop();

            if(dis[node] != cost) continue;

            for(auto [to, w] : adj[node]){

                if(cost + w < dis[to]){ 
                    parent[to].clear();
                    parent[to].push_back(node);
                    dis[to] = cost + w;
                    pq.push({dis[to], to});
                }
                else if(cost + w == dis[to]){
                    parent[to].push_back(node);
                }

            }

        }

        return parent;

    };


    fore(i, 1, n+1){
        if(i == s) continue;
        dijkstra(i, d[i]);
    }


    vector<vi> parent = dijkstraDag(s, d[s]);

    vector<bool> sirve(n+1);
    vi st;
    st.push_back(t);
    while(sz(st)){
        int cur = st.back();
        sirve[cur] = 1;
        st.pop_back();
        for(auto xx : parent[cur]){
            if(sirve[xx]) continue;
            st.push_back(xx);
        }
    }

    vector<vi> dag(n+1);

    fore(i, 1, n+1){
        for(auto xx : parent[i]){
            dag[xx].push_back(i);
        }
    }

    int ans = d[u][v];

    vector<int> dp(n+1, -1);

    auto f = [&](auto self, int node, int who) -> int {
        int &res = dp[node];
        if(sirve[node] == 0) return res = 4e18;
        if(res > -1){
            return res;
        }
        res = d[who][node];
        for(int to : dag[node]){
            res = min(res, self(self, to, who));
        }
        // cerr << "\n============\n";
        // cerr << "result para nodo " << node << ": " << res << endl;
        return res;
    };

    fore(x, 1, n+1){
        
        int res = f(f, x, v) + d[u][x];

        ans = min(ans, res);

    }

    fill(all(dp), -1);

    fore(x, 1, n+1){

        int res = f(f, x, u) + d[v][x];

        ans = min(ans, res);

    }

    // fore(i, 1, n+1){
    //     cerr << "para nodo " << i << ": ";
    //     for(auto xx : parent[i]){
    //         cerr << xx << ' ';
    //     }
    //     cerr << "\n===================\n";
    // }



    cout << ans;

}

Compilation message

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |             auto [cost, node] = pq.top();
      |                  ^
commuter_pass.cpp:55:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             for(auto [to, c] : adj[node]){
      |                      ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:74:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |             auto [cost, node] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:78:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |             for(auto [to, w] : adj[node]){
      |                      ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2928 KB Output is correct
2 Correct 11 ms 1112 KB Output is correct
3 Correct 11 ms 1112 KB Output is correct
4 Correct 46 ms 4948 KB Output is correct
5 Correct 32 ms 2736 KB Output is correct
6 Correct 16 ms 1112 KB Output is correct
7 Correct 18 ms 1372 KB Output is correct
8 Correct 29 ms 1264 KB Output is correct
9 Correct 16 ms 1368 KB Output is correct
10 Correct 34 ms 2908 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 10 ms 1116 KB Output is correct
14 Correct 13 ms 1292 KB Output is correct
15 Correct 16 ms 1116 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -