Submission #993454

#	Time	Username	Problem	Language	Result	Execution time	Memory
993454		eysbutno	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	168 ms	24832 KiB

commuter_pass

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
inline namespace IO {
    const int BUFFER_SIZE = 1 << 15;
 
    char input_buffer[BUFFER_SIZE];
    int input_pos = 0, input_len = 0;
 
    char output_buffer[BUFFER_SIZE];
    int output_pos = 0;
 
    char number_buffer[100];
    uint8_t lookup[100];
 
    void _update_input_buffer() {
        input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
        input_pos = 0;
 
        if (input_len == 0)
            input_buffer[0] = EOF;
    }
 
    inline char next_char(bool advance = true) {
        if (input_pos >= input_len)
            _update_input_buffer();
 
        return input_buffer[advance ? input_pos++ : input_pos];
    }
 
    template<typename T> 
    inline void read_int(T &number) {
        bool negative = false;
        number = 0;
 
        while (!isdigit(next_char(false)))
            if (next_char() == '-')
                negative = true;
 
        do {
            number = 10 * number + (next_char() - '0');
        } while (isdigit(next_char(false)));
 
        if (negative)
            number = -number;
    }
 
    template<typename T, typename... Args> 
    inline void read_int(T &number, Args &... args) {
        read_int(number);
        read_int(args...);
    }
 
    void _flush_output() {
        fwrite(output_buffer, sizeof(char), output_pos, stdout);
        output_pos = 0;
    }
 
    inline void write_char(char c) {
        if (output_pos == BUFFER_SIZE)
            _flush_output();
 
        output_buffer[output_pos++] = c;
    }
 
    template<typename T>
    inline void write_int(T number, char after = '\0') {
        if (number < 0) {
            write_char('-');
            number = -number;
        }
 
        int length = 0;
 
        while (number >= 10) {
            uint8_t lookup_value = lookup[number % 100];
            number /= 100;
            number_buffer[length++] = (lookup_value & 15) + '0';
            number_buffer[length++] = (lookup_value >> 4) + '0';
        }
 
        if (number != 0 || length == 0)
            write_char(number + '0');
 
        for (int i = length - 1; i >= 0; i--)
            write_char(number_buffer[i]);
 
        if (after)
            write_char(after);
    }
 
    void init() {
        // Make sure _flush_output() is called at the end of the program.
        bool exit_success = atexit(_flush_output) == 0;
        assert(exit_success);
 
        for (int i = 0; i < 100; i++)
            lookup[i] = (i / 10 << 4) + i % 10;
    }
}
constexpr ll INF = 1e18;
int main() {
    init();
    int n, m;
    read_int(n, m);
    pii a, b;
    read_int(a[0], a[1], b[0], b[1]);
    --a[0], --a[1], --b[0], --b[1];
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        read_int(u, v, w);
        adj[--u].push_back({--v, w});
        adj[v].push_back({u, w});
    }
    using pll = array<ll, 2>;
    vector<vector<int>> alt(n);
    priority_queue<pll, vector<pll>, greater<>> pq;
    {
        vector<ll> tdist(n, INF);
        pq.push({tdist[a[0]] = 0, a[0]});
        while (!pq.empty()) {
            auto [t, u] = pq.top(); pq.pop();
            if (tdist[u] != t) continue;
            for (auto [v, w] : adj[u]) {
                if (smin(tdist[v], t + w)) {
                    alt[v] = {(int) u};
                    pq.push({tdist[v], v});
                } else if (tdist[v] == t + w) {
                    alt[v].push_back((int) u);
                }
            }
        }
    }
    vector dist(2, vector(n, INF));
    for (int id = 0; id < 2; id++) {
        pq.push({dist[id][b[id]] = 0, b[id]});
        while (!pq.empty()) {
            auto [t, u] = pq.top(); pq.pop();
            if (t != dist[id][u]) continue;
            for (auto [v, w] : adj[u]) {
                if (smin(dist[id][v], t + w)) {
                    pq.push({t + w, v});
                }
            }
        }
    }
    ll res = dist[0][b[1]];
    vector<pll> dp(n, {INF, INF});
    vector<bool> vis(n);
    auto dfs = [&](int u, auto &&self) -> void {
        if (vis[u]) return;
        vis[u] = true;
        dp[u] = {dist[0][u], dist[1][u]};
        for (int v : alt[u]) {
            self(v, self);
            for (int id = 0; id < 2; id++) {
                smin(dp[u][id], dp[v][id]);
            }
        }
        for (int id = 0; id < 2; id++) {
            smin(res, dist[id][u] + dp[u][!id]);
        }
    };
    dfs(a[1], dfs);
    write_int(res, '\n');
    _flush_output();
}
/**
 * Construct an alternate graph with all the 
 * edges in possible shortest paths from S to T.
 * Any path from U to V can take any "vertical" path
 * on this alternate graph (b/c it's a DAG). So,
 * consider this alternate graph and DP on the DAG.
*/

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