Submission #883794

#	Time	Username	Problem	Language	Result	Execution time	Memory
883794		Sharky	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	365 ms	53612 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;

struct edge {
    int u, v, w;
};

int n;
vector<vector<pair<int, int>>> adj(100005), g(100005), g2(100005);
vector<edge> edges;

void dijk(int s, vector<int>& di, vector<vector<pair<int, int>>>& G) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    for (int i = 1; i <= n; i++) di[i] = INF;
    di[s] = 0;
    q.push({di[s], s});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (di[u] != d) continue;
        for (auto& [v, w] : G[u]) {
            if (di[u] + w < di[v]) {
                di[v] = di[u] + w;
                q.push({di[v], v});
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    while (m--) {
        int x, y, w;
        cin >> x >> y >> w;
        edges.push_back({x, y, w});
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    vector<int> ds(n+1), dt(n+1), d1(n+1), d2(n+1);
    dijk(s, ds, adj); dijk(t, dt, adj);
    vector<bool> nodes(n+1, 0);
    for (int i = 1; i <= n; i++) if (ds[i] + dt[i] == ds[t]) nodes[i] = 1;
    for (auto& [x, y, w] : edges) {
        if (nodes[x] && nodes[y] && ds[x] + w == ds[y]) {
            g[x].push_back({y, 0});
            g[y].push_back({x, w});
            g2[y].push_back({x, 0});
            g2[x].push_back({y, w});
        } else if (nodes[x] && nodes[y] && ds[y] + w == ds[x]) {
            g[y].push_back({x, 0});
            g[x].push_back({y, w});
            g2[x].push_back({y, 0});
            g2[y].push_back({x, w});
        } else {
            g[x].push_back({y, w});
            g[y].push_back({x, w});
            g2[x].push_back({y, w});
            g2[y].push_back({x, w});
        }
    }
    dijk(u, d1, g); dijk(u, d2, g2);
    cout << min(d1[v], d2[v]) << '\n';
}

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