Submission #1241891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241891		g4yuhg	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	197 ms	31272 KiB

commuter_pass

#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define fii first
#define sei second
const ll inf = 1e18;
const int N = 100005;

int n, m, s, t, x, y;
ll d[4][N], ans = inf;
bool vst[N];
vector<pair<int, ll>> adj[N];
vector<int> adj2[N];

struct Edge { int u, v; ll w; };
vector<Edge> edges;
ll minx[N], miny[N];

void dijkstra(int st, int id) {
    for (int i = 1; i <= n; i++) d[id][i] = inf;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    d[id][st] = 0;
    pq.push({0, st});
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist > d[id][u]) continue;
        for (auto &pr : adj[u]) {
            int v = pr.fii; ll w = pr.sei;
            if (d[id][v] > dist + w) {
                d[id][v] = dist + w;
                pq.push({d[id][v], v});
            }
        }
    }
}

void dfs2(int u) {
    vst[u] = true;
    minx[u] = miny[u] = inf;
    for (int v : adj2[u]) {
        if (!vst[v]) dfs2(v);
        ans = min(ans, d[2][u] + miny[v]);
        ans = min(ans, d[3][u] + minx[v]);
        minx[u] = min(minx[u], minx[v]);
        miny[u] = min(miny[u], miny[v]);
    }
    minx[u] = min(minx[u], d[2][u]);
    miny[u] = min(miny[u], d[3][u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> s >> t >> x >> y;
    edges.reserve(m);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges.push_back({u, v, w});
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    dijkstra(x, 2);
    dijkstra(y, 3);

    ll ST = d[0][t];
    for (int i = 1; i <= n; i++) {
        adj2[i].clear();
        vst[i] = false;
    }
    for (auto &e : edges) {
        int u = e.u, v = e.v; ll w = e.w;
        if (d[0][u] + w + d[1][v] == ST) adj2[u].push_back(v);
        if (d[0][v] + w + d[1][u] == ST) adj2[v].push_back(u);
    }

    ans = d[2][y];
    dfs2(s);
    cout << ans;
    return 0;
}

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