제출 #916506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916506		viwlesxq	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	324 ms	24148 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);
    priority_queue<pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>> q;
    q.push({0, s});
    d[s] = 0;
    while (!q.empty()) {
        int v = q.top().second;
        q.pop();
        for (auto [to, w] : g[v]) {
            if (chmin(d[to], d[v] + w)) {
                dp[0][to] = min(du[to], dp[0][v]);
                dp[1][to] = min(dv[to], dp[1][v]);
                q.push({d[to], to});
            } else if (d[to] == d[v] + w) {
                if (min(du[to], dp[0][v]) + min(dv[to], dp[1][v]) < dp[0][to] + dp[1][to]) {
                    dp[0][to] = min(du[to], dp[0][v] + w);
                    dp[1][to] = min(dv[to], dp[1][v] + w);
                }
            }
        }
    }
    //cout << s << ' ' << t << ' ' << dp[0][t] + dp[1][t] << '\n';
    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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45