Submission #1193155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193155		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	599 ms	199820 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;
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;
}

// 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, d1 [maxN], d2 [maxN] [3];
pll s1, s2;
vector <pll> adj [maxN];
vec1d trace [maxN];
priority_queue <pll, vector <pll>, greater <pll>> q;
priority_queue <lll, vector <lll>, greater <lll>> q3;
queue <ll> fq;
set <ll> mp1 [maxN], mp2 [maxN];
bool vst [maxN];

bool fin (set <ll> &x, ll y) {
    return (x. find (y) == x. end ());
}

void up (ll x, ll y, ll v) {
    if (d2 [x] [y] > v) {
        d2 [x] [y] = v;
        q3. push ({d2 [x] [y], {x, y}});
    }
}

void solve() {
    cin >> n >> m >> s1. fi >> s1. se >> s2. fi >> s2. se;
    forinc (i, 1, m) {
        ll a, b, c; cin >> a >> b >> c;
        adj [a]. pusb ({b, c});
        adj [b]. pusb ({a, c});
    }
    memset (d1, 0x3f, sizeof d1);
    d1 [s1. fi] = 0;
    q. push ({d1 [s1. fi], s1. fi});
    while (!q. empty ()) {
        pll tmp = q. top ();
        q. pop ();
        if (tmp. fi != d1 [tmp. se]) continue;
        for (pll i : adj [tmp. se]) {
            if (d1 [i. fi] > d1 [tmp. se] + i. se) {
                d1 [i. fi] = d1 [tmp. se] + i. se;
                q. push ({d1 [i. fi], i. fi});
                trace [i. fi]. clear ();
            }
            if (d1 [i. fi] == d1 [tmp. se] + i. se) trace [i. fi]. pusb (tmp. se);
        }
    }
    fq. push (s1. se);
    vst [s1. se] = 1;
    while (!fq. empty ()) {
        ll tmp = fq. front ();
        fq. pop ();
        for (ll i : trace [tmp]) {
            if (vst [i]) continue;
            mp1 [i]. insert (tmp);
            mp2 [tmp]. insert (i);
            vst [i] = 1;
            fq. push (i);
        }
    } 
    ll ans = inf64;
    memset (d2, 0x3f, sizeof d2);
    d2 [s2. fi] [0] = 0;
    q3. push ({d2 [s2. fi] [0], {s2. fi, 0}});
    while (!q3. empty ()) {
        ll val = q3. top (). fi;
        ll id  = q3. top (). se. fi; 
        ll sta = q3. top (). se. se;
        q3. pop ();
        if (val != d2 [id] [sta]) continue;
        for (pll i : adj [id]) {
            switch (sta) {
            case 0 : up (i. fi, 0, d2 [id] [sta] + i. se); break; 
            case 1 : up (i. fi, 2, d2 [id] [sta] + i. se); break;
            case 2 : up (i. fi, 2, d2 [id] [sta] + i. se); break;
            } 
            if (!fin (mp1 [id], i. fi)) {
                switch (sta) {
                case 0 : up (i. fi, 1, d2 [id] [sta]); break;
                case 1 : up (i. fi, 1, d2 [id] [sta]); break;
                }
            }
        }
    }
    forinc (i, 0, 2) mini (ans, d2 [s2. se] [i]);
    memset (d2, 0x3f, sizeof d2);
    d2 [s2. fi] [0] = 0;
    q3. push ({d2 [s2. fi] [0], {s2. fi, 0}});
    while (!q3. empty ()) {
        ll val = q3. top (). fi;
        ll id  = q3. top (). se. fi; 
        ll sta = q3. top (). se. se;
        q3. pop ();
        if (val != d2 [id] [sta]) continue;
        for (pll i : adj [id]) {
            switch (sta) {
            case 0 : up (i. fi, 0, d2 [id] [sta] + i. se); break; 
            case 1 : up (i. fi, 2, d2 [id] [sta] + i. se); break;
            case 2 : up (i. fi, 2, d2 [id] [sta] + i. se); break;
            } 
            if (!fin (mp2 [id], i. fi)) {
                switch (sta) {
                case 0 : up (i. fi, 1, d2 [id] [sta]); break;
                case 1 : up (i. fi, 1, d2 [id] [sta]); break;
                }
            }
        }
    }
    forinc (i, 0, 2) mini (ans, d2 [s2. se] [i]);
    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