Submission #228307

#	Time	Username	Problem	Language	Result	Execution time	Memory
228307		Blerargh	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	333 ms	22384 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;
typedef tuple<ll,ll,ll> tl;
typedef tuple<ll,ll,ll,ll> ql;

#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define ROF(i, a, b) for(ll i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v);
#define ALL(x) x.begin(), x.end()
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front

#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';

const ll MOD = 1e9+7; //998244353
const ll MAXN = 1e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);

int main(){
    FAST
    ll n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    ll dist1[MAXN], dist2[MAXN];
    vector<ii> adjlist[MAXN];
    FOR(i,1,n) dist1[i] = dist2[i] = INF;
    dist1[u] = dist2[v] = 0;
    FOR(i,1,m){
        ll a, b, c;
        cin >> a >> b >> c;
        adjlist[a].eb(b,c);
        adjlist[b].eb(a,c);
    }

    priority_queue<ii, vector<ii>, greater<ii> > pq;
    pq.e(0,u);
    while (!pq.empty()){
        ll dist = pq.top().f;
        ll u = pq.top().s;
        pq.pp();
        if (dist > dist1[u]) continue;
        for (auto edge : adjlist[u]){
            ll v = edge.f;
            ll cost = edge.s;
            if (dist1[u] + cost < dist1[v]){
                dist1[v] = dist1[u] + cost;
                pq.e(dist1[v], v);
            }
        }
    }

    pq.e(0,v);
    while (!pq.empty()){
        ll dist = pq.top().f;
        ll u = pq.top().s;
        pq.pp();
        if (dist > dist2[u]) continue;
        for (auto edge : adjlist[u]){
            ll v = edge.f;
            ll cost = edge.s;
            if (dist2[u] + cost < dist2[v]){
                dist2[v] = dist2[u] + cost;
                pq.e(dist2[v], v);
            }
        }
    }

    ii minuv[MAXN];
    ll mindist[MAXN];
    FOR(i,1,n) minuv[i] = mp(INF,INF), mindist[i] = INF;
    minuv[s] = mp(dist1[s], dist2[s]);
    mindist[s] = 0;

    pq.e(0,s);
    while (!pq.empty()){
        ll dist = pq.top().f;
        ll u = pq.top().s;
        pq.pp();
        if (dist > mindist[u]) continue;
        for (auto edge : adjlist[u]){
            ll v = edge.f;
            ll cost = edge.s;
            if (mindist[u] + cost < mindist[v]){
                mindist[v] = mindist[u] + cost;
                minuv[v] = mp(min(dist1[v], minuv[u].f), min(dist2[v], minuv[u].s));
                pq.e(mindist[v], v);
            } else if (mindist[u] + cost == mindist[v]){
                ll chk1 = min(dist1[v], minuv[u].f) + min(dist2[v], minuv[u].s);
                ll chk2 = minuv[v].f + minuv[v].s;
                if (chk1 < chk2) minuv[v] = mp(min(dist1[v], minuv[u].f), min(dist2[v], minuv[u].s));
            }
        }
    }
    cout << min(minuv[t].f+minuv[t].s, dist1[v]);
}

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