Submission #678591

#	Time	Username	Problem	Language	Result	Execution time	Memory
678591		jahsdwaijsd	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	280 ms	21636 KiB

commuter_pass

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define taskname "bai3"
#define all(x) x.begin(), x.end()
#define ll long long
#define ull unsigned ll
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
using namespace std;
using cd = complex<double>;

const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

int n, m, s, t, u, v;
ll dp[mxN][2][2];
vector<ll> from_u, from_v;
vector<pair<int, ll>> G[mxN];

vector<ll> dijkstra(int v) {
    vector<ll> res(n + 1, oo);
    vector<bool> vis(n + 1);
    res[v] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, v});
    while(pq.size()) {
        pair<ll, int> top = pq.top(); pq.pop();
        if(vis[top.ss])
            continue;
        vis[top.ss] = true;
        for(auto [u, w] : G[top.ss]) {
            if(res[u] > res[top.ss] + w) {
                res[u] = res[top.ss] + w;
                pq.push({-res[u], u});
            }
        }
    }
    return res;
}

void dijkstra1(int s, int t) {
    vector<ll> res(n + 1, oo);
    for(int i = 1; i <= n; ++i)
        dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = oo;
    vector<bool> vis(n + 1);
    priority_queue<pair<ll, int>> pq;
    res[s] = 0;
    dp[s][0][0] = 0;
    dp[s][0][1] = from_v[s];
    dp[s][1][0] = from_u[s];
    dp[s][1][1] = from_v[s] + from_u[s];
    pq.push({0, s});

    while(pq.size()) {
        pair<ll, int> top = pq.top(); pq.pop();
        if(vis[top.ss])
            continue;
        vis[top.ss] = true;
        for(auto [u, w] : G[top.ss]) {
            if(res[u] > res[top.ss] + w) {
                res[u] = res[top.ss] + w;
                pq.push({-res[u], u});
                dp[u][0][1] = min(dp[top.ss][0][1], from_v[u]);
                dp[u][1][0] = min(dp[top.ss][1][0], from_u[u]);
                dp[u][1][1] = min({dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]});
            }
            else if(res[u] == res[top.ss] + w) {
                dp[u][0][1] = min({dp[u][0][1], dp[top.ss][0][1], from_v[u]});
                dp[u][1][0] = min({dp[u][1][0], dp[top.ss][1][0], from_u[u]});
                dp[u][1][1] = min({dp[u][1][1], dp[top.ss][1][1], dp[top.ss][0][1] + from_u[u], dp[top.ss][1][0] + from_v[u], from_v[u] + from_u[u]});
            }
        }
    }
    cout << min(from_u[v], dp[t][1][1]) << "\n";
}

void solve() {
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    from_u = dijkstra(u);
    from_v = dijkstra(v);
    dijkstra1(s, t);
}

signed main() {
#ifdef CDuongg
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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