Submission #1248683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248683		Leo121	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	184 ms	23884 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

// #include <tr2/dynamic_bitset>
// using custom_bitset = tr2::dynamic_bitset<>;

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) v.begin(), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define fors(i, a, b, c) for(int i = a; i <= b; i += c)
#define lb lower_bound
#define ub upper_bound
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(a) cout << #a << " = " << a << ", "

//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, bool> ib;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef long double ld;
typedef double db;
//typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const ll INF = LLONG_MAX;

const int MX = 4e5;

void dijkstra(vvii & graph, vl & d, int s) {
    d[s] = 0;
    priority_queue<pli> pq;
    pq.push({0, s});
    while(!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        w = - w;
        if(d[u] != w) continue;
        for(auto & [v, w2] : graph[u]) {
            if(d[v] <= w + w2) continue;
            d[v] = w + w2;
            pq.push({- w - w2, v});
        }

    }
}

void dpf(int u, vvi & dag, ll & ans, vpll & dp, vb & vis) {
    if(vis[u]) return;
    vis[u] = 1;
    if(!SZ(dag[u])) {
        ans = min(ans, dp[u].fi + dp[u].se);
        return;
    }
    pll best = {INF, INF};
    foru(v, dag[u]) {
        dpf(v, dag, ans, dp, vis);
        best.fi = min(best.fi, dp[v].fi);
        best.se = min(best.se, dp[v].se);
    }
    ans = min(ans, dp[u].fi + best.se);
    ans = min(ans, dp[u].se + best.fi);
    dp[u].fi = min(dp[u].fi, best.fi);
    dp[u].se = min(dp[u].se, best.se);

}

void solve () {
    int n, m, s, t, a, b;
    cin >> n >> m >> s >> t >> a >> b;
    -- s, -- t, -- a, -- b;
    vl ds(n, INF), dt(n, INF), da(n, INF), db(n, INF);
    vvii graph(n);
    while(m --) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[-- u].pb({-- v, w});
        graph[v].pb({u, w});
    }
    dijkstra(graph, ds, s);
    dijkstra(graph, dt, t);
    dijkstra(graph, da, a);
    dijkstra(graph, db, b);
    vvi dagst(n);
    for0(u, n) 
        for(auto & [v, w] : graph[u]) {
            if(ds[u] + dt[v] + w != ds[t]) continue;
            dagst[u].pb(v);
        }
    vpll dp(n, {INF, INF});
    for0(u, n) 
        dp[u] = {da[u], db[u]};
    ll ans = da[b];
    vb vis(n);
    dpf(s, dagst, ans, dp, vis);
    cout << ans;
}

int main () 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // freopen("palpath.out", "w", stdout);
    // freopen("palpath.in", "r", stdin);
    int t = 1;
    // cin >> t;
    for1(i, t){
        //cout << "Case " << i << ": ";
        solve();
        cout << '\n';
    }
    return 0;
}

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