Submission #1186103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186103		nagorn_ph	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	181 ms	26736 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e5 + 5;

int n, m, st, en, x, y, ans;
bool visited[N];
vector <pii> adj[N], check;
vector <vector <int>> dp(2, vector <int> (N, inf));
vector <int> disst, disen, disx, disy;

vector <int> dijkstra(int s){
    priority_queue <pii, vector <pii>, greater <pii>> q; q.emplace(0, s);
    vector <int> dis(n + 1, inf); dis[s] = 0;
    while (!q.empty()) {
        auto [w, u] = q.top(); q.pop();
        if (w > dis[u]) continue;
        for (auto [ww, v] : adj[u]) {
            int www = w + ww;
            if (www < dis[v]) {
                dis[v] = www;
                q.emplace(dis[v], v);
            }
        }
    }
    return dis;
}

void dfs(int u){
    visited[u] = true;
    dp[0][u] = disx[u];
    dp[1][u] = disy[u];
    for (auto [ww, v] : adj[u]) {
        if (disst[v] + ww == disst[u]) {
            if (!visited[v]) dfs(v);
            dp[0][u] = min(dp[0][u], dp[0][v]);
            dp[1][u] = min(dp[1][u], dp[1][v]);
        }
    }
    ans = min({ans, dp[0][u] + disy[u], dp[1][u] + disx[u]});
    // cout << u << ": " << "\n";
    // cout << dp[0][u] << " " << disx[u] << "\n";
    // cout << dp[1][u] << " " << disy[u] << "\n";
    // cout << "-----------------------\n";
}

int32_t main(){
    iShowSpeed;
    cin >> n >> m >> st >> en >> x >> y;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].emb(w, v);
        adj[v].emb(w, u);
    }
    disst = dijkstra(st);
    disen = dijkstra(en);
    disx = dijkstra(x);
    disy = dijkstra(y);
    ans = disx[y];
    dfs(en);
    cout << ans;
}

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