Submission #959195

#	Time	Username	Problem	Language	Result	Execution time	Memory
959195		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	673 ms	55704 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <ll, ll> > adj[4*MAXN];
ll dis[4*MAXN];
bool vis[4*MAXN];

ll enc (ll u, int graphid) { return ((u<<2)|graphid); } // encode state into number
ll unenc (ll u) { return (u>>2); } // unencode
// graphid:
// 0b00 regular level 0 graph
// 0b01 foward dijkstra dag from u1 to v1 (commuter pass) level 1 graph
// 0b10 reverse dijkstra dag, same as 0b01 (commuter pass) level 1 graph
// 0b11 regular graph, same as 0b00, level 2 graph

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    ll u1, v1, u2, v2;
    cin >> u1 >> v1 >> u2 >> v2;
    u1--; v1--; u2--; v2--;
    auto addEdge = [&](ll u, ll v, ll w) { adj[u].push_back({ v, w }); };
    for (ll i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        addEdge(enc(u, 0b00), enc(v, 0b00), w); // reg graph 1 (0b00)
        addEdge(enc(v, 0b00), enc(u, 0b00), w);
        addEdge(enc(u, 0b11), enc(v, 0b11), w); // reg graph 2 (0b11)
        addEdge(enc(v, 0b11), enc(u, 0b11), w);
    }
    {priority_queue <pair <ll, ll> > pq;
    for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    dis[enc(u1, 0b00)] = 0;
    pq.push({ -dis[enc(u1, 0b00)], enc(u1, 0b00) });
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (u == enc(v2, 0b00)) break;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v] <= dis[u]+w) continue;
            dis[v] = dis[u]+w;
            pq.push({ -dis[v], v });
        }
    }
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    function <void(ll)> dfs = [&](ll u) {
        if (vis[u]) return;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v]+w != dis[u]) continue;
            cerr << unenc(v)+1 << ' ' << unenc(u)+1 << '\n';
            addEdge(enc(unenc(v), 0b01), enc(unenc(u), 0b01), 0); // dag fow (0b01)
            addEdge(enc(unenc(u), 0b10), enc(unenc(v), 0b10), 0); // dag rev (0b10)
            dfs(v);
        }
    };
    dfs(enc(v1, 0b00));}
    for (ll u = 0; u < n; u++) { // transitions between graphs
        addEdge(enc(u, 0b00), enc(u, 0b01), 0); // 0b00 to dag fow (0b01)
        addEdge(enc(u, 0b00), enc(u, 0b10), 0); // 0b00 to dag rev (0b10)
        addEdge(enc(u, 0b01), enc(u, 0b11), 0); // 0b01 to reg graph 2 (0b11)
        addEdge(enc(u, 0b10), enc(u, 0b11), 0); // 0b10 to reg graph 2 (0b11)
    }
    {priority_queue <pair <ll, ll> > pq;
    for (ll i = 0; i < 4*MAXN; i++) dis[i] = INF;
    for (ll i = 0; i < 4*MAXN; i++) vis[i] = false;
    dis[enc(u2, 0b00)] = 0;
    pq.push({ -dis[enc(u2, 0b00)], enc(u2, 0b00) });
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dis[v] <= dis[u]+w) continue;
            dis[v] = dis[u]+w;
            pq.push({ -dis[v], v });
        }
    }
    cout << dis[enc(v2, 0b11)] << '\n';}
    return 0;
}

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