Submission #1167415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167415		GoBananas69	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	363 ms	38956 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;

const ll inf = 1e18;

vector<ll> du, dv, ds, dt;
vector<ll> p, path;

vector<bool> vis;

void dijkstra(ll s, vector<ll> &dist, vector<vector<pair<ll, ll>>> &adj) {
    fill(dist.begin(), dist.end(), inf);
    fill(vis.begin(), vis.end(), false);
    priority_queue<pair<ll, ll>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        ll u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &edge: adj[u]) {
            ll v = edge.first;
            ll w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
}


void find(ll s, ll t, vector<vector<pair<ll, ll>>> &adj) {
    vector<ll> dist(adj.size(), inf);
    fill(vis.begin(), vis.end(), false); 
    priority_queue<pair<ll, ll>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        ll u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &e: adj[u]) {
            ll v = e.first;
            ll w = e.second;
            if (dist[v] > dist[u] + w) {
                p[v] = u;
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    for (ll v = t; v != s; v = p[v]) {
        path.push_back(v);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
}

signed main() {
    cin.tie() -> sync_with_stdio(0);
    ll n, m, s, t, a, b;
    cin >> n >> m >> s >> t >> a >> b;

    vector<vector<pair<ll, ll>>> adj(n + 1);
    vector<vector<pair<ll, ll>>> adj1;
    dv.resize(n + 1, inf);
    du.resize(n + 1, inf);
    ds.resize(n + 1, inf);
    dt.resize(n + 1, inf);
    p.resize(n + 1, -1);
    vis.resize(n + 1);
    
    for (ll i = 0; i<m; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dijkstra(a, du, adj);
    dijkstra(b, dv, adj);
    dijkstra(s, ds, adj);
    dijkstra(t, dt, adj);

    find(s, t, adj);
    adj1 = adj;
    for (ll i = 1; i<path.size(); ++i) {
        ll u = path[i - 1];
        ll v = path[i];
        adj1[u].push_back({v, 0});
        adj1[v].push_back({u, 0});
    }

    dijkstra(a, du, adj1);
    dijkstra(b, dv, adj1);
    ll res = min(du[b], dv[a]);
    ll res1;
    if (n <= 300) {
        vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, inf));
        for (ll i = 1; i<=n; ++i) {
            dijkstra(i, dist[i], adj);
        }
        res1 = min(du[b], dv[a]);
        for(ll i = 1; i<=n; ++i) {
            for(ll j = 1; j<=n; ++j) {
                if(ds[i] + dt[j] + dist[i][j] == ds[t]) {
                    res1 = min(res1, du[i] + dv[j]);
                    res1 = min(res1, du[j] + dv[i]);
                }
            }
        }
        res = min(res, res1);
    }
    cout << res << '\n';
}

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