Submission #1194266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194266		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	267 ms	47164 KiB

commuter_pass

// Src : Vux2Code
/* Note :
    Im dump
*/

#include <bits/stdc++.h>

using namespace std;

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

#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;
}

// Triple (+12)
struct tri {
    ll fi, se, th;
    tri(ll _fi, ll _se, ll _th) : fi(_fi), se(_se), th(_th) {}
    bool operator<(const tri& o) const {
        if (fi != o.fi) return fi < o.fi;
        if (se != o.se) return se < o.se;
        return th < o.th;
    }
    bool operator>(const tri& o) const {
        return o < *this;
    }
};


template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// 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], f [maxN] [2];
pll r1, r2;
rvs_pq <pll> pq;
rvs_pq <tri> pq2;
vector <pll> adj [maxN];
bool vst [maxN];

void dijk (ll root, ll d []) {
    // while (!pq.empty()) pq.pop(); // f
    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});
            }
        }
    }
}

ll dijk2 (ll root, ll en) {
    // while (!pq2.empty()) pq2.pop(); // f
    forinc (i, 0, n) {
        forinc (j, 0, 1) f [i] [j] = inf64; 
        vst [i] = false;
    }
    // f[0][0] = f[0][1] = inf64; // f
    pq2. push ({0, root, 0});
    while (!pq2. empty ()) {
        tri tmp = pq2. top ();
        pq2. pop ();
        if (!vst [tmp. se]) {
            vst [tmp. se] = 1; 
            ds [tmp. se] = tmp. fi; 
            f [tmp. se] [0] = min (du [tmp. se], f [tmp. th] [0]);
            f [tmp. se] [1] = min (dv [tmp. se], f [tmp. th] [1]);
            for (pll i : adj [tmp. se]) pq2. push ({tmp. fi + i. se, i. fi, tmp. se});
        }
        else if (tmp. fi == ds [tmp. se]){
            if (min (du [tmp. se], f [tmp. th] [0]) + min (dv [tmp. se], f [tmp. th] [1]) <= 
                f [tmp. se] [0] + f [tmp. se] [1]) {
                f [tmp. se] [0] = min (du [tmp. se], f [tmp. th] [0]);
                f [tmp. se] [1] = min (dv [tmp. se], f [tmp. th] [1]);        
            }
        }
    }
    return f [en] [0] + f [en] [1];
}

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});
    }
    
    dijk (r2. fi, du);  
    dijk (r2. se, dv);
    
    ll ans = du [r2. se];
    mini (ans, dijk2 (r1. fi, r1. se));
    mini (ans, dijk2 (r1. se, r1. fi));
    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: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45