Submission #453759

#	Time	Username	Problem	Language	Result	Execution time	Memory
453759		Arian_Eft	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1345 ms	65280 KiB

commuter_pass

///
///         "People's Dreams.. Never End!!"
///
///                                   ~Marshall D. Teach
#include <bits/stdc++.h>
 
using namespace std;
 
#define F first
#define S second 
#define pb push_back
#define mk make_pair
#define endl cout << '\n'
#define haha cerr << "haha\n"
#define all(x) x.begin(), x.end()
#define kill(x) exit((cout << (x) << '\n', 0))
#define yn(flag) ((flag) ? "YES\n": "NO\n")
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2")
ll const inf = 1'000'000'000'000'000 + 10;
ll const mod = 1'000'000'000 + 7;
ll const maxn = 300'000 + 10;
ll const base = 337;
ll const sq = 320;
ll n;
ll dis[maxn];
set<pll> s;
vector<pll> adj[maxn];
vector<ll> vec[maxn];

ll dij(ll x, ll y) {
    fill(dis, dis + 3 * n, inf);
    dis[x] = 0;
    s.clear();
    s.insert(mk(0, x));
    while (s.size()) {
        auto [d, v] = *s.begin();
        s.erase(mk(d, v));
        for (auto [u, w] : adj[v]) {
            if (dis[u] > d + w) {
                s.erase(mk(dis[u], u));
                dis[u] = d + w;
                s.insert({dis[u], u});
                vec[u].clear();
                vec[u].pb(v);
            } else if (dis[u] == d + w) {
                vec[u].pb(v);
            }
        }
    }
    return dis[y];
}

bool mark[maxn];

void build1() {
    for (ll i = n; i < 2 * n; ++i) {
        if (mark[i - n])
            for (auto u : vec[i - n]) {
                adj[u + n].pb({i, 0});
            }
    }
    for (ll i = 2 * n; i < 3 * n; ++i) {
        for (auto u : adj[i - 2 * n])
            adj[i].pb({u.F + 2 * n, u.S});
    }
    for (ll i = 0; i < n; ++i) {
        adj[i].pb({i + n, 0});
        adj[i + n].pb({i + 2 * n, 0});
    }
}


void dfs(ll v) {
    mark[v] = true;
    for (auto u : vec[v]) {
        if (!mark[u])
            dfs(u);
    }
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    ll m;
    cin >> n >> m;
    ll a, b, u, v;
    cin >> a >> b >> u >> v;
    --a, --b, --u, --v;
    for (ll i = 0; i < m; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        adj[a].pb(mk(b, c));
        adj[b].pb(mk(a, c));
    }
    dij(a, b);
    dfs(b);
    build1();
    cout << min(dij(u, v + n + n), dij(v, u + n + n)) << '\n';
}

// check before submiting : 
// maxn (please check this shit)

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