Submission #1180812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180812		patgra	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	309 ms	68308 KiB

commuter_pass

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;
    
int n, m, S, T, U, V;
vector<vector<pair<int, ll>>> g, g2;
vector<ll> distFromS, distFromT, dist;
ll want;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> S >> T >> U >> V;
    g.resize(n + 1);
    int a, b, c;
    rep(i, 0, m) cin >> a >> b >> c, g[a].pb({b, c}), g[b].pb({a, c});
    distFromS.resize(n + 1, 1e18), distFromT.resize(n + 1, 1e18);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> Q;
    distFromS[S] = 0;
    Q.push({0, S});
    while(!Q.empty()) {
        auto [md, v] = Q.top();
        Q.pop();
        if(md > distFromS[v]) continue;
        repIn2(u, d, g[v]) if(md + d < distFromS[u]) distFromS[u] = md + d, Q.push({md + d, u});
    }
    DEBUG {
        DC << "distFromS: ";
        rep(i, 1, n + 1) DC << distFromS[i] << ' ';
        DC << eol;
    }
    distFromT[T] = 0;
    Q.push({0, T});
    while(!Q.empty()) {
        auto [md, v] = Q.top();
        Q.pop();
        if(md > distFromT[v]) continue;
        repIn2(u, d, g[v]) if(md + d < distFromT[u]) distFromT[u] = md + d, Q.push({md + d, u});
    }
    DEBUG {
        DC << "distFromT: ";
        rep(i, 1, n + 1) DC << distFromT[i] << ' ';
        DC << eol;
    }
    want = distFromS[T];
    DC << "want = " << want << eol;

    g2.resize((n + 1) * 4);
    rep(v, 1, n + 1) {
        g2[v].pb({v + 2 * n, 0});
        g2[v].pb({v + 3 * n, 0});
        g2[v + 2 * n].pb({v + n, 0});
        g2[v + 3 * n].pb({v + n, 0});
        repIn2(u, d, g[v]) {
            g2[v].pb({u, d}), g2[v + n].pb({u + n, d});
            if(distFromS[v] + distFromT[v] == want && distFromS[u] + distFromT[u] == want) {
                if(distFromS[u] == distFromS[v] + d) g2[v + 2 * n].pb({u + 2 * n, 0});
                if(distFromS[v] == distFromS[u] + d) g2[v + 3 * n].pb({u + 3 * n, 0});
            }
        }
    }

    dist.resize((n + 1) * 4, 1e18);
    dist[V] = 0;
    Q.push({0, V});
    DC << "Dist: " << eol;
    while(!Q.empty()) {
        auto [md, v] = Q.top();
        Q.pop();
        if(md > dist[v]) continue;
        if(v <= n) { DC << " O" << v; }
        else if(v <= 2 * n) { DC << " X" << v - n; }
        else if(v <= 3 * n) { DC << " T" << v - 2 * n; }
        else { DC << " S" << v - 3 * n; }
        DC << " (" << v << ") " << ' ' << md << eol;
        repIn2(u, d, g2[v]) {
            DC << "   -> ";
            if(u <= n) { DC << " O" << u; }
            else if(u <= 2 * n) { DC << " X" << u - n; }
            else if(u <= 3 * n) { DC << " T" << u - 2 * n; }
            else { DC << " S" << u - 3 * n; }
            DC << ' ' << d << eol;
            if(md + d < dist[u]) dist[u] = md + d, Q.push({md + d, u});
        }
    }

    DC << U + n << eol;
    cout << dist[U + n] << '\n';
}

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