Submission #1138425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138425		anmattroi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	287 ms	25136 KiB

commuter_pass

#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, m, S, T, U, V;

int64_t kc[maxn], ck[maxn];
vector<ii> adj[maxn];
vector<int> g[maxn];
vector<int> tg[maxn];
int64_t tc[maxn], ct[maxn];

void dijkstra1() {
    for (int i = 1; i <= n; i++) kc[i] = ck[i] = LLONG_MAX/2;
    kc[S] = ck[T] = 0;
    set<pair<int64_t, int> > q;
    q.insert({0, S});
    while (!q.empty()) {
        int u = q.begin()->se; q.erase(q.begin());
        for (auto [v, l] : adj[u])
        if (kc[v] > kc[u] + l) {
            q.erase({kc[v], v});
            kc[v] = kc[u] + l;
            q.insert({kc[v], v});
        }
    }
    q.insert({0, T});
    while (!q.empty()) {
        int u = q.begin()->se; q.erase(q.begin());
        for (auto [v, l] : adj[u])
        if (ck[v] > ck[u] + l) {
            q.erase({ck[v], v});
            ck[v] = ck[u] + l;
            q.insert({ck[v], v});
        }
    }
}

void dijkstra2() {
    for (int i = 1; i <= n; i++) tc[i] = ct[i] = LLONG_MAX/2;
    tc[U] = ct[V] = 0;
    set<pair<int64_t, int> > q;
    q.insert({0, U});
    while (!q.empty()) {
        int u = q.begin()->se; q.erase(q.begin());
        for (auto [v, l] : adj[u])
        if (tc[v] > tc[u] + l) {
            q.erase({tc[v], v});
            tc[v] = tc[u] + l;
            q.insert({tc[v], v});
        }
    }
    q.insert({0, V});
    while (!q.empty()) {
        int u = q.begin()->se; q.erase(q.begin());
        for (auto [v, l] : adj[u])
        if (ct[v] > ct[u] + l) {
            q.erase({ct[v], v});
            ct[v] = ct[u] + l;
            q.insert({ct[v], v});
        }
    }
}

int x[maxn], id = 0, cl[maxn];

void dfs(int u) {
    cl[u] = 1;
    for (int v : g[u])
        if (!cl[v]) dfs(v);
    x[++id] = u;
}

int64_t A[maxn], B[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        adj[u].emplace_back(v, l);
        adj[v].emplace_back(u, l);
    }
    dijkstra1(); dijkstra2();
    int64_t mindis = kc[T];

    for (int u = 1; u <= n; u++)
        for (auto [v, l] : adj[u]) {
            if (kc[u] + l + ck[v] == mindis) {
                g[u].emplace_back(v);
                tg[v].emplace_back(u);
            }
        }
    int64_t ans = tc[V];
//    cout << "------------------\n";
//    for (int i = 1; i <= n; i++) cout << tc[i] << ' ' << ct[i] << "\n";
//    cout << "------------------\n";
    for (int i = 1; i <= n; i++) if (!cl[i]) dfs(i);

    for (int i = 1; i <= n; i++) {
        A[i] = tc[i];
        B[i] = ct[i];
    }

    for (int i = 1; i <= n; i++) {
        int u = x[i];
        for (int v : g[u]) A[u] = min(A[u], A[v]);
    }
    for (int i = n; i >= 1; i--) {
        int u = x[i];
        for (int v : tg[u]) B[u] = min(B[u], B[v]);
    }
    for (int i = 1; i <= n; i++) ans = min(ans, A[i] + B[i]);

    for (int i = 1; i <= n; i++) {
        A[i] = ct[i];
        B[i] = tc[i];
    }

    for (int i = 1; i <= n; i++) {
        int u = x[i];
        for (int v : g[u]) A[u] = min(A[u], A[v]);
    }
    for (int i = n; i >= 1; i--) {
        int u = x[i];
        for (int v : tg[u]) B[u] = min(B[u], B[v]);
    }
    for (int i = 1; i <= n; i++) ans = min(ans, A[i] + B[i]);


    cout << ans;
}
/*
 6 6
 1 6
 1 4
 1 2 1
 2 3 1
 3 5 1
 2 4 3
 4 5 2
 5 6 1
 */

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