Submission #1102201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102201		_8_8_	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	352 ms	41072 KiB

commuter_pass

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
    
const int  N = 3e5 + 12, MOD = 998244353;
ll inf = 1e18;
int n, m, s, t, u, v;
vector<pair<int, int>> g[N];
vector<int> G[N];
vector<array<int, 3>> e;
vector<ll> dijkstra(vector<int> vec) {
    vector<ll> d(n, inf);
    set<pair<ll ,int>> st;
    for(int i:vec) {
        st.insert({0, i});
        d[i] = 0;
    }
    while(!st.empty()) {
        int v = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to, w]:g[v]) {
            if(d[to] > d[v]  + w) {
                st.erase({d[to], to});
                d[to] = d[v] + w;
                st.insert({d[to], to});
            }
        }
    }
    return d;
}
vector<int> ord;
bool vis[N];
ll dp[N], pd[N];
void dfs(int v) {
    vis[v] = 1;
    for(int to:G[v]) {
        if(!vis[to]) {
            dfs(to);
        }
    }
    ord.push_back(v);
}
void test() {
    cin >> n >> m;
    cin >> s >> t >> v >> u;
    s--;t--;u--;v--;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;v--;
        e.push_back({u, v, w});
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<ll> d = dijkstra({s}), dn = dijkstra({t});
    ll D = d[t];
    for(auto [x, y, w]:e) {
        if(D == w + d[x] + dn[y]) {
            G[x].push_back(y);
        } 
        else if(D == w + d[y] + dn[x]) {
            G[y].push_back(x);
        }
    }
    for(int i = 0; i < n; i++) {
        if(!vis[i] && !G[i].empty()) {
            dfs(i);
        }
    }
    vector<ll> du = dijkstra({u}), dv = dijkstra({v});
    ll res = du[v];
    for(int i:ord) {
        // cout << i + 1 << ' ';
        dp[i] = du[i];
        pd[i] = dv[i];
        for(int to:G[i]) {
            dp[i] = min(dp[i], dp[to]);
            pd[i] = min(pd[i], pd[to]);
        }
        res = min({res, dp[i] + dv[i], pd[i] + du[i]});
    }
    // cout << '\n';
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

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