Submission #1013091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013091		aufan	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	250 ms	31324 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inff = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m;
        cin >> n >> m;

        int s, t;
        cin >> s >> t;

        int u, v;
        cin >> u >> v;

        vector<vector<pair<int, int>>> g(n + 1);
        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});
        }
        
        auto dijkstra = [&](int x) {
                vector<int> dist(n + 1, inff);
                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
                dist[x] = 0;
                pq.push({dist[x], x});
                while (!pq.empty()) {
                        auto [w, x] = pq.top();
                        pq.pop();

                        if (w > dist[x]) continue;

                        for (auto [z, c] : g[x]) {
                                if (w + c < dist[z]) {
                                        dist[z] = w + c;
                                        pq.push({dist[z], z});
                                }
                        }
                }

                return dist;
        };

        auto ds = dijkstra(s);
        auto dt = dijkstra(t);
        auto du = dijkstra(u);
        auto dv = dijkstra(v);
        
        vector<int> imp(n + 1);
        for (int i = 1; i <= n; i++) {
                if (ds[i] + dt[i] == ds[t]) {
                        imp[i] = 1;
                }
        }

        vector<vector<int>> h(n + 1);
        for (int i = 1; i <= n; i++) {
                if (imp[i]) {
                        for (auto [j, c] : g[i]) {
                                if (imp[j] && ds[i] + c == ds[j]) {
                                        h[i].push_back(j);
                                }
                        }
                }
        }

        int ans = du[v];
        vector<int> dp(n + 1);

        function<int(int)> dfs = [&](int x) {
                if (dp[x] != -1) return dp[x];

                int mn = dv[x];
                for (auto z : h[x]) {
                        mn = min(mn, dfs(z));
                }

                ans = min(ans, du[x] + mn);

                return dp[x] = mn;
        };
        
        dp.assign(n + 1, -1);
        dfs(s);
        swap(du, dv);
        dp.assign(n + 1, -1);
        dfs(s);

        cout << ans << '\n';
        
        return 0;
}

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