Submission #99149

#	Time	Username	Problem	Language	Result	Execution time	Memory
99149		noclever	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	740 ms	23264 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const long long INF = (long long) 1e18;

template<typename T>
struct edge {
    int from, to;
    T cost;
};

void dijkstra(const vector< vector< edge<long long> > >& g, int s, vector<long long>& dist) {
    dist.assign((int) g.size(), INF);
    dist[s] = 0;
    priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
    pq.push({0, s});
    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d < dist[u]) {
            continue;
        }
        for (auto& v : g[u]) {
            if (d + v.cost < dist[v.to]) {
                dist[v.to] = d + v.cost;
                pq.push({dist[v.to], v.to});
            }
        }
    }
}

void calc_dp(const vector< vector< edge<long long> > >& g, const vector<long long>& dist, const vector<long long>& dist2, int s, vector<long long>& dp) {
    queue<int> que;
    que.push(s);
    dp.assign((int) g.size(), INF);
    dp[s] = dist[s];
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto& v : g[u]) {
            if (dist2[u] + v.cost == dist2[v.to]) {
                if (dp[v.to] > dp[u]) {
                    que.push(v.to);
                    dp[v.to] = min({dp[u], dist[v.to]});
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    vector< vector< edge<long long> > > g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        g[a].push_back({a, b, c});
        g[b].push_back({b, a, c});
    }
    vector<long long> dist_u, dist_v, dist_s, dist_t, dp1, dp2;
    dijkstra(g, u, dist_u);
    dijkstra(g, v, dist_v);
    dijkstra(g, s, dist_s);
    dijkstra(g, t, dist_t);
    calc_dp(g, dist_v, dist_s, s, dp1);
    calc_dp(g, dist_v, dist_t, t, dp2);
    long long ans = INF;
    for (int i = 1; i <= n; i++) {
        if (dist_s[i] + dist_t[i] == dist_s[t]) {
            ans = min(ans, dist_u[i] + min(dp1[i], dp2[i]));
        }
    }
    cout << min(ans, dist_u[v]) << '\n';
    return 0;
}

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