Submission #1217855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217855		thimphu	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2098 ms	63732 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, m, s, t, u, v;

void dfs(vector<vector<pair<int, int>>>& adj, int i, vector<bool>& visited, int& c, int cw, vector<map<pair<int, int>, bool>>& free, vector<int>& par) {
    if (i == t and cw == c) {
        int t = i;
        map<pair<int, int>, bool> tmp;
        while (par[t] != -1) {
            tmp[make_pair(t, par[t])] = true;
            t = par[t];
        }
        free.push_back(tmp);
        return;
    }
    visited[i] = true;
    for (auto& [j, w] : adj[i]) {
        if (visited[j] or cw + w > c) continue;
        par[j] = i;
        dfs(adj, j, visited, c, cw + w, free, par);
    }
    visited[i] = false;
}

int dijkstra(vector<vector<pair<int, int>>>& adj, map<pair<int, int>, bool>& free) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dis2(n, LLONG_MAX);
    dis2[u] = 0;
    pq.push({0, u});
    while (!pq.empty()) {
        auto [curw, curn] = pq.top();
        pq.pop();
        if (curw > dis2[curn]) continue;
        for (auto& [nextn, nextw] : adj[curn]) {
            if (free.find(make_pair(nextn, curn)) != free.end() or free.find(make_pair(curn, nextn)) != free.end()) {
                if (curw < dis2[nextn]) {
                    dis2[nextn] = curw;
                    pq.push({dis2[nextn], nextn});
                }
            } else {
                if (curw + nextw < dis2[nextn]) {
                    dis2[nextn] = curw + nextw;
                    pq.push({dis2[nextn], nextn});
                }
            }
        }
    }
    return dis2[v];
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> s >> t >> u >> v;
    s--;
    t--;
    u--;
    v--;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    vector<int> dis(n, LLONG_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    dis[s] = 0;
    while (!pq.empty()) {
        auto [curw, curn] = pq.top();
        pq.pop();
        if (curw > dis[curn]) continue;
        for (auto& [nextn, nextw] : adj[curn]) {
            if (curw + nextw < dis[nextn]) {
                dis[nextn] = curw + nextw;
                pq.push({dis[nextn], nextn});
            }
        }
    }
    vector<bool> visited(n);
    vector<map<pair<int, int>, bool>> free;
    vector<int> par(n, -1);
    dfs(adj, s, visited, dis[t], 0, free, par);
    // for (auto& i : free) {
    //     for (auto& [ff, ss] : i) cout << ff.second + 1 << '|' << ff.first + 1 << ' ';
    //     cout << '\n';
    // }
    int ans = LLONG_MAX;
    for (auto& i : free) {
        // cout << dijkstra(adj, i) << ' ';
        ans = min(ans, dijkstra(adj, i));
    }
    cout << ans;
}

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