Submission #1046638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046638		VMaksimoski008	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	135 ms	26212 KiB

commuter_pass

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int n, m, S, T, U, V;
vector<pii> graph[maxn+5];
vector<int> G[maxn+5];
vector<array<int, 3> > edges;
ll dist[3][maxn+5];

void D(int s, int t) {
    priority_queue<pll, vector<pll>, greater<pll> > pq;
    for(int i=1; i<=n; i++) dist[t][i] = 1e18;
    dist[t][s] = 0; pq.push({ 0, s });

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d != dist[t][u]) continue;

        for(auto &[v, w] : graph[u]) {
            if(dist[t][v] > d + w) {
                dist[t][v] = d + w;
                pq.push({ d + w, v });
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m >> S >> T >> U >> V;

    for(int i=0; i<m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({ a, b, w });
        graph[a].push_back({ b, w });
        graph[b].push_back({ a, w });
    }

    D(S, 0);
    D(U, 1);
    D(V, 2);

    vector<int> in(n+1), topo; queue<int> q; 
    for(auto &[a, b, w] : edges) {
        if(dist[0][a] + w == dist[0][b]) G[a].push_back(b), in[b]++;
        if(dist[0][b] + w == dist[0][a]) G[b].push_back(a), in[a]++;
    }

    q.push(S);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for(int &v : G[u]) if(--in[v] == 0) q.push(v);
    }

    vector<ll> dpU(n+1, 1e18), dpV(n+1, 1e18), dp(n+1, 1e18);
    dpU[S] = dist[1][S]; dpV[S] = dist[2][S]; dp[S] = dpU[S] + dpV[S];

    for(int &u : topo) {
        dp[u] = min({ dp[u], dpU[u] + dist[2][u], dpV[u] + dist[1][u] });
        for(int &v : G[u]) {
            dp[v] = min(dp[v], dp[u]);
            dpU[v] = min({ dpU[v], dpU[u], dist[1][v] });
            dpV[v] = min({ dpV[v], dpV[u], dist[2][v] });
        }
    }

    cout << min(dp[T], dist[1][V]) << '\n';
    return 0;
}

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