Submission #1157132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157132		tsengang	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	310 ms	23716 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
const int MOD = 998244353;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll INF = 1e18;
vector<pair<ll, ll>> v[100004];
ll n, m, S, T, U, V;
ll dist[100004][3];
ll dp[100004][4];
void djikstra(ll d, ll i) {
    set<pair<ll, ll>> s;
    s.insert({0, d});
    dist[d][i] = 0;
    while (!s.empty()) {
        auto p = *s.begin();
        s.erase(s.begin());
        if (dist[p.ss][i] != p.ff) continue;
        for (auto [x, y] : v[p.ss]) {
            if (p.ff + y < dist[x][i]) {
                s.erase({dist[x][i], x});
                dist[x][i] = p.ff + y;
                s.insert({dist[x][i], x});
            }
        }
    }
}
ll get(ll x, ll v) {
    ll res = 0;
    if (v & 1) res += dist[x][1];
    if (v & 2) res += dist[x][2];
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> S >> T >> U >> V;
    for (ll i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].pb({b, c});
        v[b].pb({a, c});
    }
    for (ll i = 0; i <= n; i++) {
        for (ll j = 0; j < 3; j++) dist[i][j] = INF;
    }
    djikstra(S, 0);
    djikstra(U, 1);
    djikstra(V, 2);
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < 4; j++) dp[i][j] = INF;
    }
    vector<pair<ll, ll>> ds(n + 1);
    for (ll i = 1; i <= n; i++) {
        ds[i] = {dist[i][0], i};
    }
    sort(ds.begin() + 1, ds.end());
    dp[S][0] = 0;
    dp[S][1] = dist[S][1];
    dp[S][2] = dist[S][2];
    dp[S][3] = dist[S][1] + dist[S][2];
    for (ll z = 1; z <= n; z++) {
        ll i = ds[z].ss;
        for (auto [j, w] : v[i]) {
            if (dist[i][0] + w != dist[j][0]) continue;
            for (ll l = 0; l < 4; l++) {
                for (ll k = 0; k < 4; k++) {
                    dp[j][l | k] = min(dp[j][l | k], dp[i][l] + get(j, k));
                }
            }
        }
    }
    ll ans = min(dp[T][3], dist[V][1]);
    cout << ans;
}

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