제출 #993454

#제출 시각아이디문제언어결과실행 시간메모리
993454eysbutnoCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
168 ms24832 KiB
#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. */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...