Submission #859004

#	Time	Username	Problem	Language	Result	Execution time	Memory
859004		Pring	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	414 ms	37944 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<int, pii> p3i;

const int MXN = 100005, INF = 3000000000000000000;
int n, m, s, t, u, v, ans;
int dp[MXN], dp_v[MXN], dis[MXN], dis_v[MXN];
vector<pii> edge[MXN];
vector<int> DAG[MXN], DAG_INV[MXN];

inline void DIJKSTRA(int sr, int *dis, bool rec) {
    priority_queue<p3i, vector<p3i>, greater<p3i>> pq;
    fill(dis + 1, dis + n + 1, -1);
    pq.push(mp(0LL, mp(0LL, sr)));
    while (pq.size()) {
        p3i now = pq.top();
        pq.pop();
        int x = now.fs, p = now.sc.fs, id = now.sc.sc;
        if (rec) {
            if (dis[id] == x || dis[id] == -1) {
                DAG[id].push_back(p);
            }
            if (dis[id] != -1) continue;
            dis[id] = x;
        } else {
            if (dis[id] != -1) continue;
            dis[id] = x;
        }
        for (auto &e : edge[id]) {
            pq.push(mp(x + e.fs, mp(id, e.sc)));
        }
    }
}

void DFS(int id) {
    for (auto &i : DAG[id]) {
        if (DAG_INV[i].empty()) DFS(i);
        DAG_INV[id].push_back(i);
    }
}

inline void MAKE_DAG_INV() {
    DAG[s].pop_back();
    // DFS(t);
    // for (int i = 1; i < n; i++) DAG[i].clear();
    // for (int id = 1; id <= n; id++) {
    //     for (auto &i : DAG_INV[id]) DAG[i].push_back(id);
    // }
}

void DFS2(int id) {
    dp[id] = dis[id];
    dp_v[id] = dis_v[id];
    for (auto &i : DAG[id]) {
        if (dp[i] == -1) DFS2(i);
        dp[id] = min(dp[id], dp[i]);
        dp_v[id] = min(dp_v[id], dp_v[i]);
    }
    ans = min(ans, dp[id] + dis_v[id]);
    ans = min(ans, dp_v[id] + dis[id]);
}

inline void DP() {
    fill(dp + 1, dp + n + 1, -1);
    fill(dp_v + 1, dp_v + n + 1, -1);
    dp[s] = dis[s];
    dp_v[s] = dis_v[s];
    ans = min(ans, dis[s] + dis_v[s]);
    DFS2(t);
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    int x, y, z;
    cin >> n >> m >> s >> t >> u >> v;
    while (m--) {
        cin >> x >> y >> z;
        edge[x].push_back(mp(z, y));
        edge[y].push_back(mp(z, x));
    }
    DIJKSTRA(s, dis, true);
    MAKE_DAG_INV();
    DIJKSTRA(u, dis, false);
    DIJKSTRA(v, dis_v, false);
    ans = dis[v];
    DP();
    cout << ans << endl;
    return 0;
}

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