Submission #1230071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230071		goldenbull	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	196 ms	66860 KiB

commuter_pass

#include <bits/stdc++.h>

///----------------[shorthand macros]---------------------------------------
#define fi              first
#define se              second

#define pb              push_back
#define all(x)          x.begin(), x.end()
#define cast(a, b)      static_cast<a>(b)

#define MASK(n)        ((n >= 64 ? ~0ULL : ((1ULL << (n)) - 1ULL)))
#define BIT(n, i)      (((n) >> (i)) & 1)
#define SET(n, i)      (n = ((n) | (1 << (i))))
#define UNSET(n, i)    (n = ((n) & ~(1 << (i))))
#define FLIP(n, i)     (n = ((n) ^ (1 << (i))))

#define el '\n'

using namespace std;

///-------------[type aliases & structs]------------------------------------
template <typename T>
using ve    = vector<T>;
using ll    = long long;
using ull   = unsigned ll;
using db    = double;
using vi    = ve<int>;
using vll   = ve<ll>;
using vdb   = ve<db>;
using vb    = ve<bool>;
using ii    = pair<int, int>;
using pll   = pair<ll, ll>;

struct edge
{
    int u, v, w;
    int other(int k)
    {
        return u ^ v ^ k;
    }
};

struct node
{
    int nu=0, nv=0;
    ll res = 2e15+7;
};

///--------------------[constants]------------------------------------------
const ll MAX = 1e6 + 7;
const ll MOD = 1e9 + 7;
const ll inf = 2e15 + 7;

///---------------------[globals]-------------------------------------------
int n, m, s, t, u, v;
edge edges[MAX];
vi adj[MAX];

ll dist1[MAX];
ll dist2[MAX];
bool vis[MAX];
vi e_trace[MAX];

bool in_dijkstra[MAX];

///-----------------[helper functions]--------------------------------------
template <typename T>
void print(T arr[], int n)
{
    for (int i = 0; i < n; i++) cout << arr[i] << ' '; cout << el;
}

void dijkstra(int st, ll dist[], bool vis[], vi e_trace[] = nullptr)
{
    // initialization
    fill(dist+1, dist+n+1, inf);
    fill(vis+1, vis+n+1, false);
    if (e_trace != nullptr)
        for (int i = 1; i <= n; i++) e_trace[i].clear();

    // the juicy part
    priority_queue<pll, ve<pll>, greater<pll>> sus;
    dist[st] = 0;
    sus.push({0, st});

    while (!sus.empty())
    {
        int cur = sus.top().se;
        sus.pop();

        if (vis[cur]) continue;
        vis[cur] = true;

        for (auto i : adj[cur])
        {
            int v = edges[i].other(cur);
            ll w = edges[i].w;

            if (dist[cur] + w < dist[v])
            {
                dist[v] = dist[cur] + w;
                sus.push({dist[v], v});

                if (e_trace != nullptr)
                {
                    e_trace[v].clear();
                    e_trace[v].pb(i);
                }
            }
            else if (dist[cur] + w == dist[v])
            {
                if (e_trace != nullptr)
                    e_trace[v].pb(i);
            }
        }
    }
}

void dfs(int cur, int p, vi adj[], bool vis[], vi& topo)
{
    if (vis[cur]) return;
    vis[cur] = true;

    for (auto i : adj[cur])
    {
        int v = edges[i].other(cur);
        if (v == p) continue;
        dfs(v, cur, adj, vis, topo);
    }

    topo.pb(cur);
}

///------------------[main execution]---------------------------------------
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);

    // input
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a,b,c};
        adj[a].pb(i);
        adj[b].pb(i);
    }

    // solve
    dijkstra(s, dist1, vis, e_trace);
    dijkstra(u, dist1, vis);
    dijkstra(v, dist2, vis);

    vi topo;
    fill(vis+1, vis+n+1, false);
    dfs(t, t, e_trace, vis, topo);
    reverse(all(topo));

    ve<node> dp(n+1);
    dp[topo[0]] = {topo[0], topo[0], dist1[topo[0]] + dist2[topo[0]]};
    for (auto i : topo)
    {
        for (auto j : e_trace[i])
        {
            int v = edges[j].other(i);

            int a = (dist1[v] < dist1[dp[i].nu] ? v : dp[i].nu);
            int b = (dist2[v] < dist2[dp[i].nv] ? v : dp[i].nv);
            ll c = dist1[a] + dist2[b];
//            cout << v << " -> " << a << ' ' << b << " -> " << c << el;

            if (c < dp[v].res) dp[v] = {a, b, c};
        }
    }

//    for (auto i: topo) cout << i << ' '; cout << el;
//    for (auto i : dp) cout << i.res << ' '; cout << el;

    cout << min(dist1[v], dp[s].res);

    return 0;
}

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