Submission #883057

#	Time	Username	Problem	Language	Result	Execution time	Memory
883057		viwlesxq	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	262 ms	37244 KiB

commuter_pass

//     ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//     ➡  IOI, IZhO ⬅
//     ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
//⠀⠀⢠⣤⡄⢠⣤⣤⣤⣤⣤⣤⡄⢠⣤⡄⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠙⠃⠘⠛⠛⠛⠛⠛⠛⠃⠘⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀  ⠘⠛⠛⠛⠛⠛⠛⠛⠛⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⣠⣶⣶⠂⣰⣶⣶⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⢀⣾⣿⣿⡏⢠⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⡈⠻⣿⣿⣶⣾⣿⣿⣿⣿⠿⠋⡀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⣿⣶⣄⠙⣿⣿⣿⣿⣟⢁⣴⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⢹⣿⡏⢠⣿⠟⠛⢿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠙⠀⠀⣠⣶⣷⣤⡈⠛⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠋⠉⠀⠀


#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
#define pb push_back
#define eb emplace_back

template<typename S>
bool chmin(S &a, const S b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename S>
bool chmax(S &a, const S b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const double eps = 1e-6;
const double EPS = 1e-9;

const int N = 1e5 + 1;

vector<pair<int, int>> g[N];
vector<int> d(N, INF), p(N, -1), parent(N);
map<pair<int, int>, bool> used;
vector<tuple<int, int, int>> edge;
 
void dijkstra(int init) {
    priority_queue<pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>> q;
    q.push({0, init});
    d[init] = 0;
    while (!q.empty()) {
        int v = q.top().second;
        q.pop();
        for (auto [to, w] : g[v]) {
            int add = (used[{v, to}] ? 0 : w);
            if (chmin(d[to], d[v] + add)) {
                p[to] = v;
                q.emplace(d[to], to);
            }
        }
    }
}

int find_set(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void unite(int u, int v) {
    u = find_set(u), v = find_set(v);
    if (u == v) {
        return;
    }
    parent[u] = v;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    int a[m], b[m], c[m];
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        edge.eb(c[i], a[i], b[i]);
    }
    sort(all(edge), greater<tuple<int, int, int>>());
    iota(all(parent), 0);
    while (!edge.empty() && (find_set(u) != find_set(v) || find_set(s) != find_set(t))) {
        int w = get<0>(edge.back()), x = get<1>(edge.back()), y = get<2>(edge.back());
        edge.pop_back();
        g[x].eb(y, w);
        g[y].eb(x, w);
        unite(x, y);
    }
    dijkstra(s);
    int x = t;
    while (p[x] != -1) {
        used[{p[x], x}] = used[{x, p[x]}] = true;
        x = p[x];
    }
    fill(all(d), INF);
    dijkstra(u);
    cout << d[v];
}

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