Submission #869718

#	Time	Username	Problem	Language	Result	Execution time	Memory
869718		sleepntsheep	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	411 ms	33344 KiB

commuter_pass

#include <iostream>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")



using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005

int n, m, s, t, cs, ct, head[N], e, se, shead[N], is[N];
struct edge
{
    int w, v, u, next;
} g[N<<1], sg[N<<1];

ll dp_cs[N], dp_ct[N], dp_s_[N], dp_t_[N], dp_u[N], dp_v[N], ans = 1e18;
ll *dp_s = dp_s_, *dp_t = dp_t_;

void add_edge(int u, int v, int w, struct edge *g, int *e, int *h)
{
    int p = (*e)++;
    g[p] = {w, v, u, h[u]}; h[u] = p;
}

void add_biedge(int u, int v, int w, struct edge *g, int *e, int *h)
{
    add_edge(u, v, w, g, e, h), add_edge(v, u, w, g, e, h);
}

void dijkstra(ll *d, int s = -5)
{
    set<pair<ll, int>> h;
    if (s == -5)
    {
        for (int u = 1; u <= n; ++u) if (d[u] == 0) h.emplace(0, u);
    }
    else
        h.emplace(d[s] = 0, s);
    for (; h.size(); )
    {
        auto [c, u] = *h.begin(); h.erase(h.begin());
        for (auto i = head[u]; i != -1; i = g[i].next)
        {
            auto [w, v, U, _] = g[i];
            if (c + w < d[v]) h.erase({d[v], v}), h.emplace(d[v] = c + w, v);
        }
    }
}

void dijkstra2(ll *d, int s)
{
    set<pair<ll, int>> h;
    for (h.emplace(d[s] = 0, s); h.size(); )
    {
        auto [c, u] = *h.begin(); h.erase(h.begin());
        for (auto i = head[u]; i != -1; i = g[i].next)
        {
            auto [w, v, U, _] = g[i];
            if (dp_s[u] + dp_t[v] + w == dp_s[t] || dp_s[v] + dp_t[u] + w == dp_s[t])
                w = 0;
            if (c + w < d[v]) h.erase({d[v], v}), h.emplace(d[v] = c + w, v);
        }
    }
}

void init()
{
    memset(dp_ct, 63, sizeof dp_ct);
    memset(dp_cs, 63, sizeof dp_cs);
    memset(head, -1, sizeof head);
    ShinLena;
    cin >> n >> m >> s >> t >> cs >> ct;
    for (int u, v, w, i = 0; i < m; ++i) cin >> u >> v >> w, add_biedge(u, v, w, g, &e, head);
    dijkstra(dp_cs, cs);
    dijkstra(dp_ct, ct);
    ans = dp_cs[ct];
}

int C=0;
void build_shortest_path_graph()
{
    ++C;
    memset(shead, -1, sizeof shead);
    memset(dp_s, 63, sizeof dp_s_);
    memset(dp_t, 63, sizeof dp_t_);
    dijkstra(dp_s, s);
    dijkstra(dp_t, t);
    se = 0;
    for (int j = 0; j < e; ++j)
    {
        auto [w, v, u, _] = g[j];
        if (dp_s[u] + dp_t[v] + w == dp_s[t] ||
                dp_s[v] + dp_t[u] + w == dp_s[t])
        {
            if (!C&&dp_s[u] > dp_s[v]) continue;
            else if (C&&dp_s[u] > dp_s[v]) continue;
            add_edge(u, v, w, sg, &se, shead), is[u] = is[v] = 1;
        }
    }
}

int vs[N];
void dfs(int u, int p, ll w)
{
    dp_u[u] = min(dp_cs[u], dp_u[p]);
    dp_v[u] = min(dp_ct[u], dp_v[p]);
    vs[u]=1;
    for (auto j = shead[u]; j != -1; j = sg[j].next)
    {
        auto [w, v, U, _] = sg[j];
        if (vs[v]) continue;
        {
            dp_u[v] = 1ll*w+dp_u[u];
            dp_v[v] = 1ll*w+dp_v[u];
            dfs(v, u, w);
        }
    }
}

void find_path(int s, int t)
{
    memset(dp_u, 63, sizeof dp_u);
    memset(dp_v, 63, sizeof dp_v);
    memset(vs, 0, sizeof vs);
    dfs(s, s, 0);

    ans = min(ans, dp_u[t] + dp_v[t]);
}

int main()
{
    init();
    build_shortest_path_graph();
    find_path(s, t);
    swap(t, s);
    swap(cs, ct);
    build_shortest_path_graph();
    find_path(s, t);
    cout << ans;

    return 0;
}

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