Submission #865461

#	Time	Username	Problem	Language	Result	Execution time	Memory
865461		Asamai	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	274 ms	20676 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 1e5 + 5;
const ll inf = 1e18;

int n, m, S, T, U, V;
vector<pii> adj[MAX_N];
int distU[MAX_N], distV[MAX_N], distS[MAX_N], back[MAX_N];
int dp[MAX_N][2];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int ans = inf;

void dijkstra1(int start, int *dist) {
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (currW + w < dist[v]) {
                dist[v] = currW + w;
                pq.push({dist[v], v});
            }
        }
    }
}

void sol(int start, int end) {
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = distS[i] = inf;
    }
    distS[start] = 0;
    dp[start][0] = distU[start];
    dp[start][1] = distV[start];

    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        if (currW > distS[u]) {
            continue;
        }

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;

            if (currW + w > distS[v]) {
                continue;
            }

            if (currW + w == distS[v]) {
                minimize(dp[v][0], dp[u][0]);
                minimize(dp[v][1], dp[u][1]);
            }
            else {
                distS[v] = currW + w;
                pq.push({distS[v], v});
                dp[v][0] = min(dp[u][0], distU[v]);
                dp[v][1] = min(dp[u][1], distV[v]);
            }
        }
    }

    dijkstra1(end, back);

    for (int i = 1; i <= n; i++) {
        bool ok = false;
        for (auto it : adj[i]) {
            int v = it.fi;
            int w = it.se;
            if (distS[i] + w + back[v] == distS[end]) {
                ok = true;
                break;
            }
        }
        if (ok) {
            minimize(ans, dp[i][0] + dp[i][1]);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    dijkstra1(U, distU);
    dijkstra1(V, distV);

    sol(S, T);
    sol(T, S);

    cout << ans;

    return 0;
}

/*


Tuesday, 24 October 2023
15:16:46
*/

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