Submission #538438

#	Time	Username	Problem	Language	Result	Execution time	Memory
538438		MohamedFaresNebili	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	467 ms	31124 KiB

commuter_pass

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;
        using db = double;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()
        #define lb lower_bound
        #define ub upper_bound

        const ll INF = LONG_LONG_MAX / 2;

        using pi = pair<ll, ii>;

        ll n, m, s, t, u, v;
        vector<array<ll, 2>> adj[100001];
        ll disU[100001], disV[100001];
        ll dp[2][100001], res;

        void dijkstra(ll src, ll arr[]) {
            for(ll l = 1; l <= n; l++) arr[l] = INF;
            priority_queue<ii, vector<ii>, greater<ii>> pq;
            arr[src] = 0; pq.push({0, src});
            while(!pq.empty()) {
                ll a = pq.top().ss; ll w = pq.top().ff; pq.pop();
                if(arr[a] < w) continue;
                for(auto e : adj[a]) {
                    ll len = e[1] + w; ll to = e[0];
                    if(arr[to] <= len) continue;
                    arr[to] = len; pq.push({len, to});
                }
            }
        }
        void dijkstra0() {
            for(ll l = 0; l <= n; l++) dp[0][l] = dp[1][l] = INF;
            priority_queue<pi, vector<pi>, greater<pi>> pq;
            pq.push({0, {s, 0}}); vector<bool> vis(n + 1, 0);
            vector<long long> dis(n + 1, INF);
            while(!pq.empty()) {
                ll a = pq.top().ss.ff, par = pq.top().ss.ss;
                ll w = pq.top().ff; pq.pop();
                if(!vis[a]) {
                    vis[a] = 1; dis[a] = w;
                    dp[0][a] = min(disU[a], dp[0][par]);
                    dp[1][a] = min(disV[a], dp[1][par]);
                    for(auto u : adj[a]) {
                        pq.push({u[1] + w, {u[0], a}});
                    }
                }
                else if(w == dis[a])
                    if(min(dp[0][par], disU[a]) + min(dp[1][par], disV[a]) <= dp[0][a] + dp[1][a]) {
                        dp[0][a] = min(disU[a], dp[0][par]);
                        dp[1][a] = min(disV[a], dp[1][par]);
                    }
            }
            res = min(res, dp[0][t] + dp[1][t]);
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m >> s >> t >> u >> v;
            for(ll l = 0; l < m; l++) {
                ll x, y; ll w; cin >> x >> y >> w;
                adj[x].pb({y, w}); adj[y].pb({x, w});
            }
            dijkstra(u, disU); dijkstra(v, disV);
            res = disU[v]; dijkstra0();
            swap(s, t); dijkstra0();
            cout << res << "\n";
        }

/**
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
**/

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