Submission #882180

#	Time	Username	Problem	Language	Result	Execution time	Memory
882180		viwlesxq	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	633 ms	46348 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 = 998244353;
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);
map<pair<int, int>, bool> used;

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);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t, u, v;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].eb(b, c);
        g[b].eb(a, c);
    }
    dijkstra(s);
    vector<int> path;
    int x = t;
    while (x != -1) {
        path.pb(x);
        x = p[x];
    }
    reverse(all(path));
    for (int i = 0; i + 1 < size(path); ++i) {
        used[{path[i], path[i + 1]}] = true;
    }
    fill(all(d), INF);
    dijkstra(u);
    cout << d[v];
}

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