Submission #1089647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089647		ivan_alexeev	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1470 ms	146744 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

const ll inf = 1'000'000'000'000'000'000;

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")


//#define int long long

struct reb{
    int a;
    int b;
    ll c;
};

vector<ll> dij(vector<vector<pair<int, ll>>> v, int start){
    int n = v.size();
    vector<ll> d(n, inf);
    d[start] = 0;
    set<pair<ll, int>> s;
    for(int i = 0; i < n; i++){
        s.insert({d[i], i});
    }
    while(!s.empty()){
        auto [dist, u] = *s.begin();
        s.erase(s.begin());
        for(auto [i, j] : v[u]){
            if(dist + j < d[i]){
                s.erase({d[i], i});
                d[i] = dist + j;
                s.insert({d[i], i});
            }
        }
    }
    return d;
}

void solve(){
    int n, m;
    cin >> n >> m;
    int s, t;
    cin >> s >> t;
    int s1, t1;
    cin >> s1 >> t1;
    s--;t--;s1--;t1--;
    vector<reb> r;
    vector<vector<pair<int, ll>>> v(n);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        r.push_back({a, b, c});
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
    auto ds = dij(v, s);
    auto dt = dij(v, t);
    vector<vector<pair<int, ll>>> v1(3 * n), v2(3 * n);
    for(auto [a, b, c] : r){
        if(ds[a] + c + dt[b] == ds[t]){
            v1[n + a].emplace_back(n + b, 0);
            v2[n + b].emplace_back(n + a, 0);
        }
        if(ds[b] + c + dt[a] == ds[t]){
            v1[n + b].emplace_back(n + a, 0);
            v2[n + a].emplace_back(n + b, 0);
        }
        v1[a].emplace_back(b, c);
        v1[b].emplace_back(a, c);
        v1[2 * n + a].emplace_back(2 * n + b, c);
        v1[2 * n + b].emplace_back(2 * n + a, c);

        v2[a].emplace_back(b, c);
        v2[b].emplace_back(a, c);
        v2[2 * n + a].emplace_back(2 * n + b, c);
        v2[2 * n + b].emplace_back(2 * n + a, c);
    }
    for(int i = 0; i < n; i++){
        v1[i].emplace_back(i + n, 0);
        v1[i + n].emplace_back(i + 2 * n, 0);
        v2[i].emplace_back(i + n, 0);
        v2[i + n].emplace_back(i + 2 * n, 0);
    }
    auto d = dij(v1, s1);
    auto d1 = dij(v2, s1);
    cout << min(d[t1 + 2 * n], d1[t1 + 2 * n]) << endl;
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << setprecision(5) << fixed;
    int _ = 1;
    //cin >> t;
    while(_--){
        solve();
    }
    return 0;
}

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