Submission #973213

#	Time	Username	Problem	Language	Result	Execution time	Memory
973213		shezitt	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	280 ms	32068 KiB

commuter_pass

#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 = 1e5+5;

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

        }
    };

    vi du(n+1, 4e18), dv(n+1, 4e18), ds(n+1, 4e18);

    dijkstra(u, du);
    dijkstra(v, dv);

    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;

    };

    vector<vi> parent = dijkstraDag(s, ds);

    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 = du[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;
        }
        if(who == u){
            res = du[node];
        } else {
            res = dv[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) + du[x];

        ans = min(ans, res);

    }

    fill(all(dp), -1);

    fore(x, 1, n+1){

        int res = f(f, x, u) + dv[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 (stderr)

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:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |             auto [cost, node] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:81:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |             for(auto [to, w] : adj[node]){
      |                      ^

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45