Submission #1193768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193768		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	425 ms	206332 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(" \t");
            auto r = token.find_last_not_of(" \t");
            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); }

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});
    }
    // 1. Dijkstra từ s1.fi, giữ trace các cha
    memset(d1, 0x3f, sizeof d1);
    d1[s1.fi] = 0;
    q.push({0, s1.fi});
    while (!q.empty()) {
        auto [dist, u] = q.top(); q.pop();
        if (dist != d1[u]) continue;
        for (auto &e : adj[u]) {
            ll v = e.fi, w = e.se;
            if (d1[v] > dist + w) {
                d1[v] = dist + w;
                trace[v].clear();
                trace[v].pusb(u);
                q.push({d1[v], v});
            } else if (d1[v] == dist + w) {
                trace[v].pusb(u);
            }
        }
    }
    // 2. Xây mp1/mp2 cho mọi cạnh trên DAG (cung trên đường ngắn nhất)
    //    rồi BFS để tìm các đỉnh thực sự nằm trên DAG
    forinc(i, 1, n) {
        for (ll p : trace[i]) {
            mp1[p].insert(i);
            mp2[i].insert(p);
        }
    }
    memset(vst, 0, sizeof vst);
    fq.push(s1.se);
    vst[s1.se] = true;
    while (!fq.empty()) {
        ll u = fq.front(); fq.pop();
        for (ll p : trace[u]) {
            // ghi nhận cung nếu chưa có, nhưng BFS qua đỉnh mỗi đỉnh một lần
            if (!vst[p]) {
                vst[p] = true;
                fq.push(p);
            }
        }
    }
    ll ans = inf64;
    // 3. Dijkstra đa trạng thái từ s2.fi
    memset(d2, 0x3f, sizeof d2);
    d2[s2.fi][0] = 0;
    q3.push({0, {s2.fi, 0}});
    while (!q3.empty()) {
        auto [val, st] = q3.top(); q3.pop();
        ll u = st.fi, sta = st.se;
        if (val != d2[u][sta]) continue;
        for (auto &e : adj[u]) {
            ll v = e.fi, w = e.se;
            bool isDAG = mp1[u].count(v) > 0;
            if (isDAG) {
                // miễn phí nếu đang state 0 hoặc 1
                if (sta == 0 || sta == 1) up(v, 1, val);
                else /* sta==2 */ up(v, 2, val + w);
            } else {
                ll cost = val + w;
                if (sta == 0) up(v, 0, cost);
                else        up(v, 2, cost);
            }
        }
    }
    mini(ans, d2[s2.se][0]);
    mini(ans, d2[s2.se][1]);
    mini(ans, d2[s2.se][2]);
    // 4. Lặp lại với hoán đổi s1.se <-> s1.fi (đảo chiều đường ngắn nhất)
    memset(d2, 0x3f, sizeof d2);
    d2[s2.fi][0] = 0;
    q3.push({0, {s2.fi, 0}});
    while (!q3.empty()) {
        auto [val, st] = q3.top(); q3.pop();
        ll u = st.fi, sta = st.se;
        if (val != d2[u][sta]) continue;
        for (auto &e : adj[u]) {
            ll v = e.fi, w = e.se;
            bool isDAG = mp2[u].count(v) > 0;
            if (isDAG) {
                if (sta == 0 || sta == 1) up(v, 1, val);
                else                        up(v, 2, val + w);
            } else {
                ll cost = val + w;
                if (sta == 0) up(v, 0, cost);
                else        up(v, 2, cost);
            }
        }
    }
    mini(ans, d2[s2.se][0]);
    mini(ans, d2[s2.se][1]);
    mini(ans, d2[s2.se][2]);
    // So sánh với không dùng vé
    // ... nếu cần, so sánh với khoảng cách trực tiếp
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (t--) solve();
    return 0;
}

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