Submission #481399

#	Time	Username	Problem	Language	Result	Execution time	Memory
481399		Shin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	304 ms	37404 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

int n, m, s, t, U, V;
bool can[N];
long long dp[2][N];
vector<int> g[N], f[N];
vector<pair<int, int>> adj[N];
vector<long long> dist_u, dist_v;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n + 7, INFLL);
    priority_queue<pair<long long, int>> heap;
    heap.push(mp(0, s));
    dist[s] = 0;

    while (!heap.empty()) {
        int u; long long d_u;
        tie(d_u, u) = heap.top(); heap.pop();
        d_u = -d_u;

        if (dist[u] != d_u) continue;
        for (pair<int, int> v: adj[u]) if (minimize(dist[v.fi], v.se + d_u)) {
            heap.push(mp(-dist[v.fi], v.fi));
        }
    }
    return dist;
}


void dfs1(int u) {
    dp[0][u] = dist_v[u];
    for (int v: g[u]) {
        if (dp[0][v] == -1) dfs1(v);
        minimize(dp[0][u], dp[0][v]);
    }
}
void dfs2(int u) {
    dp[1][u] = dist_v[u];
    for (int v: f[u]) {
        if (dp[1][v] == -1) dfs2(v);
        minimize(dp[1][u], dp[1][v]);
    }
}

void solve(void) {
    cin >> n >> m >> s >> t >> U >> V;
    for (int i = 1; i <= m; i ++) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    dist_u = dijkstra(U);
    dist_v = dijkstra(V);   
    vector<long long> dist(dijkstra(s));
    vector<long long> _dist(dijkstra(t));
    for (int u = 1; u <= n; u ++) {
        for (pair<int, int> v: adj[u]) {
            if (_dist[v.fi] + v.se + dist[u] == dist[t]) {
                can[v.fi] = can[u] = true;
                g[u].push_back(v.fi);
                f[v.fi].push_back(u);
            }
        }
    }

    memset(dp, -1, sizeof dp);
    dfs1(s);
    dfs2(t);

    long long res = dist_u[V];
    for (int i = 1; i <= n; i ++) if (can[i]) {
        minimize(res, dist_u[i] + min(dp[0][i], dp[1][i]));
    }
    cout << res;
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0);
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

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