Submission #916512

#	Time	Username	Problem	Language	Result	Execution time	Memory
916512		viwlesxq	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	380 ms	33744 KiB

commuter_pass

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

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 1e5 + 1;

vector<pair<int, int>> g[N];
vector<int> du(N, INF), dv(N, INF);
vector<vector<int>> dp(2, vector<int> (N, INF));
int res;

void dijkstra(int init, vector<int> &d) {
    priority_queue<pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>> q;
    q.push({0, init});
    d[init] = 0;
    while (!q.empty()) {
        int v = q.top().second;
        q.pop();
        for (auto [to, w] : g[v]) {
            if (chmin(d[to], d[v] + w)) {
                q.push({d[to], to});
            }
        }
    }
}

void compute(int s, int t) {
    vector<int> d(N, INF);
    vector<bool> vis(N, false);
    priority_queue<array<int, 3>,
        vector<array<int, 3>>,
        greater<array<int, 3>>> q;
    q.push({0, s, 0});
    d[s] = 0;
    while (!q.empty()) {
        auto [c, v, p] = q.top();
        q.pop();
        if (!vis[v]) {
            vis[v] = true;
            d[v] = c;
            dp[0][v] = min(du[v], dp[0][p]);
            dp[1][v] = min(dv[v], dp[1][p]);
            for (auto [to, w] : g[v]) q.push({c + w, to, v});
        } else if (c == d[v]) {
            if (min(du[v], dp[0][p]) + min(dv[v], dp[1][p]) <= dp[0][v] + dp[1][v]) {
                dp[0][v] = min(du[v], dp[0][p]);
                dp[1][v] = min(dv[v], dp[1][p]);
            }
        }
    }
    chmin(res, dp[0][t] + dp[1][t]);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    dijkstra(u, du), dijkstra(v, dv);
    res = min(du[v], dv[u]);
    compute(s, t), compute(t, s);
    cout << res;
} 

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