Submission #1193766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193766		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	208 ms	112780 KiB

commuter_pass

// Src : Vux2Code
/* Note :

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define fi first
#define se second   

#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}

// debug (+20)
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template<typename... Args>
void debug_impl(const char* names, Args&&... args) {
    vector<string> _names;
    {
        istringstream ss(names);
        string token;
        while (getline(ss, token, ',')) {
            auto l = token.find_first_not_of(" 	");
            auto r = token.find_last_not_of(" 	");
            if (l == string::npos) _names.push_back("");
            else _names.push_back(token.substr(l, r - l + 1));
        }
    }
    cerr << "(";
    size_t _i = 0;
    int _dummy[] = { 0, ((cerr << _names[_i] << " : " << args << (++_i < _names.size() ? ", " : "")), 0)... };
    (void)_dummy;
    cerr << ")" << endl;
}

// handy for loops
#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))

#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())

const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }

/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;

/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }

ll t = 1;

ll n, m, ds [maxN], du [maxN], dv [maxN], du2 [maxN], dv2 [maxN];
pll r1, r2;
priority_queue <pll, vector <pll>, greater <pll>> pq;
queue <ll> q;
vector <pll> adj [maxN];
vec1d topo, pr [maxN], ch [maxN];
bool ckTopo [maxN];

void dijk (ll root, ll d []) {
    fill (d, d + n + 1, inf64);
    d [root] = 0;
    pq. push ({d [root], root});
    while (!pq. empty ()) {
        ll dis = pq. top (). fi; 
        ll id  = pq. top (). se; 
        pq. pop ();
        if (dis != d [id]) continue;
        for (pll i : adj [id]) {
            if (d [i. fi] > d [id] + i. se) {
                d [i. fi] = d [id] + i. se;
                pq. push ({d [i. fi], i. fi});
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    cin >> r1. fi >> r1. se; 
    cin >> r2. fi >> r2. se;
    forinc (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w; 
        adj [u]. pusb ({v, w});
        adj [v]. pusb ({u, w});
    }
    memset (ds, 0x3f, sizeof ds);
    ds [r1. fi] = 0;
    pq. push ({ds [r1. fi], r1. fi}); 
    while (!pq. empty ()) {
        ll dis = pq. top (). fi; 
        ll id = pq. top (). se;
        pq. pop ();
        if (dis != ds [id]) continue;
        for (pll i : adj [id]) {
            if (ds [i. fi] > ds [id] + i. se) {
                ds [i. fi] = ds [id] + i. se;
                pq. push ({ds [i. fi], i. fi}); 
                pr [i. fi]. clear ();
            }
            if (ds [i. fi] == ds [id] + i. se) pr [i. fi]. pusb (id);
        }
    }
    q. push (r1. se);
    ckTopo [r1. se] = 1;
    while (!q. empty ()) {
        ll tmp = q. front ();
        q. pop ();
        topo. pusb (tmp);
        for (ll i : pr [tmp]) if (!ckTopo [i]) {
            q. push (i);
            ch [i]. pusb (tmp);
            ckTopo [i] = 1;
        }
    }
    dijk (r2. fi, du);  
    dijk (r2. se, dv);
    
    ll ans = du [r2. se];
    // for (ll i : topo) cerr << i << ' '; cerr << '\n';
    memset (du2, 0x3f, sizeof du2);
    memset (dv2, 0x3f, sizeof dv2);
    for (ll i : topo) {
        mini (du2 [i], du [i]);
        mini (dv2 [i], dv [i]);
        for (ll j : pr [i]) {
            mini (du2 [j], du2 [i]);
            mini (dv2 [j], dv2 [i]);
        }
        mini (ans, du2 [i] + dv [i]);
        mini (ans, dv2 [i] + du [i]);
        // cerr << i << ' ' << min (du2 [i] + dv [i], dv2 [i] + du [i]) << '\n';
    }
    reverse (topo. begin (), topo. end ());
    memset (du2, 0x3f, sizeof du2);
    memset (dv2, 0x3f, sizeof dv2);
    for (ll i : topo) {
        mini (du2 [i], du [i]);
        mini (dv2 [i], dv [i]);
        for (ll j : ch [i]) {
            mini (du2 [j], du2 [i]);
            mini (dv2 [j], dv2 [i]);
        }
        mini (ans, du2 [i] + dv [i]);
        mini (ans, dv2 [i] + du [i]);
        // cerr << i << ' ' << min (du2 [i] + dv [i], dv2 [i] + du [i]) << '\n';
    }
    // forinc (i, 1, n) {
    //     cerr << i << ' ' << ds [i] << ' ' << du [i] << ' ' << dv [i] << ' ' << du2 [i] << ' ' << dv2 [i] << '\n';
    // }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    // cin >> t;
    while (t--) solve();
}

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