Submission #501191

#	Time	Username	Problem	Language	Result	Execution time	Memory
501191		radal	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	585 ms	25144 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 1e5+20,mod = 1e9+7,inf = 1e18+10,sq = 32000;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
ll d[4][N],my[N],mx[N];
int par[4][N];
int s,t,x,y;
vector<pll> adj[N];
void dij(int i){
    set<pair<ll,int> > st;
    if (i == 0){
        st.insert({0,s});
        d[0][s] = 0;
        par[0][s] = -1;
        my[s] = d[3][s];
        mx[s] = d[2][s];
    }
    if (i == 1){
        st.insert({0,t});
        d[1][t] = 0;
        par[1][t] = -1;
    }
    if (i == 2){
        st.insert({0,x});
        d[2][x] = 0;
        par[2][x] = -1;
    }
    if (i == 3){
        st.insert({0,y});
        d[3][y] = 0;
        par[3][y] = -1;
    }
    while (!st.empty()){
        auto p = *(st.begin());
        int v = p.Y;
        st.erase(st.begin());
        for (auto u : adj[v]){
            if (d[i][u.X] > d[i][v] + u.Y){
                st.erase({d[i][u.X],u.X});
                par[i][u.X] = v;
                if (!i){
                    my[u.X] = d[3][u.X];
                    mx[u.X] = d[2][u.X];
                }
                d[i][u.X] = d[i][v] + u.Y;
                st.insert({d[i][u.X],u.X});
            }
            if (!i && d[i][u.X] == d[i][v] + u.Y){
                my[u.X] = min(my[u.X],my[v]);
                mx[u.X] = min(mx[u.X],mx[v]);
            }
        }
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    memset(d,63,sizeof d);
    int n,m;
    cin >> n >> m >> s >> t  >> x >> y;
    rep(i,0,m){
        ll u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    repr(i,3,0) dij(i);
    ll ans = d[2][y];
    rep(i,1,n+1){
        if(d[0][i]+d[1][i] == d[0][t]) ans = min({ans,my[i]+d[2][i],mx[i]+d[3][i]});
    }
    cout << ans;
}

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