Submission #595110

#	Time	Username	Problem	Language	Result	Execution time	Memory
595110		Vanilla	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	572 ms	27348 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
vector <pair <int, int64> > ad [maxn];
int64 d [3][maxn];
int64 dp [2][maxn]; 
bitset <maxn> vis;

int main() {
    int n,m, s1, t1, s2, t2;
    cin >> n >> m >> s1 >> t1 >> s2 >> t2;
    for (int i = 0; i < maxn; i++) for (int j = 0; j < 3; j++) d[j][i] = 1e18;
    for (int i = 0; i < m; i++){
        int x,y,c;
        cin >> x >> y >> c;
        ad[x].push_back({y, c});
        ad[y].push_back({x, c});
    }
    auto dijkstra = [&] (int start, int idx) {
        set <pair <int64, int64> > s;
        d[idx][start] = 0;
        s.insert({0, start});
        while (!s.empty()) {
            int u = s.begin()->second;
            s.erase(s.begin());
            for (auto &[v, cost]: ad[u]) {
                if (d[idx][u] + cost < d[idx][v]) {
                    s.erase({d[idx][v], v});
                    d[idx][v] = d[idx][u] + cost;
                    s.insert({d[idx][v], v});
                }
            }
        }
    };
    dijkstra(s2, 0);
    dijkstra(t2, 1);
    dijkstra(s1, 2);
    int64 rs = d[0][t2];
    auto dfs = [&] (int u, auto&& dfs) -> void {
        vis[u] = 1;
        dp[0][u] = d[0][u]; // s2 -> u
        dp[1][u] = d[1][u]; // t2 -> u
        for (auto &[v, cost]: ad[u]) {
            if (d[2][u] - cost != d[2][v]) continue;
            if (!vis[v]) dfs(v, dfs);
            dp[0][u] = min(dp[0][u], dp[0][v]);
            dp[1][u] = min(dp[1][u], dp[1][v]);
        }
        rs = min(rs, min(dp[0][u] + d[1][u], dp[1][u] + d[0][u]));
    };
    dfs(t1, dfs);
    cout << rs << "\n";
    return 0;
}

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