Submission #1182003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182003		anteknne	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	189 ms	29216 KiB

commuter_pass

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define pil pair<ll, ll>
#define pli pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 200 * 1000 + 1;
vector<pil> graf[MAXN];
ll odl[MAXN];
ll odlS[MAXN];
ll odlT[MAXN];
ll odlU[MAXN];
ll odlV[MAXN];
ll dp[MAXN][4];
vector<pli> vec;
priority_queue<pil> pq;

void djikstra (ll s) {
    //memset(odl, ll(INT_MAX) * ll(MAXN), sizeof(odl));
    for (int i = 1; i < MAXN; i ++) {
        odl[i] = 1e18;
        //cout << odl[i];
    }

    /*for (int i = 1; i <= 8; i ++) {
        cout << odl[i] << " ";
    }*/

    odl[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        ll v = pq.top().nd;
        ll vodl = -pq.top().st;
        pq.pop();
        if (vodl > odl[v]) {
            continue;
        }
        for (auto x : graf[v]) {
            if (vodl + x.nd < odl[x.st]) {
                odl[x.st] = vodl + x.nd;
                pq.push({-odl[x.st], x.st});
            }
        }
    }
}

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

    ll n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;

    ll a, b;
    ll c;
    for (ll i = 0; i < m; i ++) {
        cin >> a >> b >> c;
        graf[a].pb({b, c});
        graf[b].pb({a, c});
    }

    djikstra(S);
    swap(odl, odlS);
    djikstra(T);
    swap(odl, odlT);
    djikstra(U);
    swap(odl, odlU);
    djikstra(V);
    swap(odl, odlV);

    if (debug) {
        cout << "odlS:\n";
        for (ll i = 1; i <= n; i ++) {
            cout << i << ": " << odlS[i] << "\n";
        }
        cout << "\n";
    }

    for (ll i = 1; i <= n; i ++) {
        vec.pb({odlS[i], i});
    }

    sort(vec.begin(), vec.end());

    //memset(dp, ll(INT_MAX) * ll(MAXN), sizeof(dp));
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < 4; j ++) {
            dp[i][j] = 1e18;
        }
    }

    dp[S][0] = 0;
    dp[S][1] = odlU[S];
    dp[S][2] = odlV[S];
    dp[S][3] = odlU[S] + odlV[S];

    for (auto x : vec) {
        ll v = x.nd;
        for (auto x : graf[v]) {
            if (odlS[v] == odlS[x.st] + x.nd) {
                for (ll i = 0; i < 4; i ++) {
                    for (ll j = 0; j < 4; j ++) {
                        ll dod = 0;
                        if (j & 1) {
                            dod += odlU[x.st];
                        }
                        if (j & 2) {
                            dod += odlV[x.st];
                        }
                        if (odlU[x.st] == 1e18 || odlV[x.st] == 1e18 || dp[x.st][i] == 1e18) {
                            continue;
                        }
                        dp[v][i | j] = min(dp[v][i | j], dp[x.st][i] + dod);

                    }
                }
            }
        }
    }

    cout << min(dp[T][3], odlU[V]) << "\n";



    return 0;
}

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