Submission #1256366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256366		yerazh	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2091 ms	14588 KiB

commuter_pass

#include <bits/stdc++.h>

#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

using namespace std;

const int maxn = 1e5 + 5, inf = 2e9;

int n, m, s, t, u, v;
vector<pii> g[maxn];
bool is_min[maxn]{};

void mark_mins() {
    vector<int> dist(n, inf);
    bool used[n]{};
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(mp(0, s));

    while (len(pq) > 0) {
        auto [curr_dst, curr] = pq.top(); pq.pop();
        if (dist[curr] != inf) {
            continue;
        }
        dist[curr] = curr_dst;
        if (curr == t) {
            break;
        }
        for (auto [to, cst] : g[curr]) {
            if (dist[to] == inf) {
                pq.push(mp(curr_dst + cst, to));
            }
        }
    }
    
    queue<int> q;
    q.push(t);
    while (len(q) > 0) {
        int curr = q.front(); q.pop();
        is_min[curr] = 1;
        for (auto [to, cst] : g[curr]) {
            if (dist[to] == dist[curr] - cst) {
                q.push(to);
            }
        }
    }
}

void solve2() {
    mark_mins();

    bool used[n]{};
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(mp(0, v));
    while (len(pq) > 0) {
        auto [dist, curr] = pq.top(); pq.pop();
        if (used[curr]) {
            continue;
        }
        used[curr] = 1;
        if (is_min[curr]) {
            cout << dist << "\n";
            return;
        }
        
        for (auto [to, cst] : g[curr]) {
            if (!used[to]) {
                pq.push(mp(dist + cst, to));   
            }
        }
    }
    throw 1;
}

void solve() {
    cin >> n >> m >> s >> t >> u >> v;
    --s; --t; --u; --v;
    for (int i = 0; i < m; i++) {
        int from, to, cst;
        cin >> from >> to >> cst; --from; --to;
        g[from].pb(mp(to, cst));
        g[to].pb(mp(from, cst));
    }
    
    if (s == u) {
        solve2();
    }
}

int main()
{
  cin.tie(nullptr)->sync_with_stdio(false);
 
  int t = 1;
//   cin >> t;
  while (t--)
    solve();
}

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