Submission #963091

#	Time	Username	Problem	Language	Result	Execution time	Memory
963091		toast12	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	302 ms	30236 KiB

commuter_pass

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

const long long INF = 1e18;

int n, m;
int s, t, u, v;
vector<vector<pair<int, long long>>> adj;
vector<vector<int>> p;
vector<bool> visited;
vector<bool> on_path;
vector<bool> processed;

void dfs(int cur) {
    if (processed[cur])
        return;
    on_path[cur] = true;
    processed[cur] = true;
    for (auto x : p[cur]) {
        dfs(x);
    }
}

void dijkstras(vector<vector<int>> &parent, vector<long long> &dist, int start) {
    priority_queue<pair<long long, int>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        if (visited[x])
            continue;
        visited[x] = true;
        for (auto e : adj[x]) {
            long long w = e.second;
            if (w + dist[x] < dist[e.first]) {
                parent[e.first].clear();
                parent[e.first].push_back(x);
                dist[e.first] = dist[x]+w;
                pq.push({-dist[e.first], e.first});
            }
            else if (w + dist[x] == dist[e.first]) {
                parent[e.first].push_back(x);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    p.resize(n+1);
    processed.resize(n+1);
    on_path.resize(n+1);
    visited.resize(n+1);
    cin >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        int x, y;
        long long w;
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    p[s].push_back(s);
    vector<long long> d(n+1, INF);
    d[s] = 0;
    dijkstras(p, d, s);
    for (auto x : p[t]) {
        dfs(x);
    }
    on_path[t] = true;
    vector<vector<int>> temp(n+1);
    vector<long long> dv(n+1, INF);
    dv[v] = 0;
    fill(visited.begin(), visited.end(), false);
    dijkstras(temp, dv, v);
    long long ans = INF;
    long long mnv = INF;
    for (int i = 1; i <= n; i++) {
        if (!on_path[i])
            continue;
        mnv = min(mnv, dv[i]);
        ans = min(ans, mnv);
    }
    cout << ans << '\n';
    return 0;
}

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