Submission #1100973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100973		Ejen	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	287 ms	39892 KiB

commuter_pass

#include <bits/stdc++.h>

#define el "\n"
#define fu(i, a, b) for (int i = a; i <= b; ++i)
#define fd(i, a, b) for (int i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r) (rng);
}

ll last(ll msk)     {return msk & (-msk);}
ll pop_cnt(ll msk)  {return __builtin_popcountll(msk);}
ll ctz(ll msk)      {return __builtin_ctzll(msk);}
ll lg(ll msk)       {return 63 - __builtin_clzll(msk);}

template<class T1, class T2> bool minimize(T1 &a, T2 b) {
    return a > b ? a = b, 1 : 0;
}

template<class T1, class T2> bool maximize(T1 &a, T2 b) {
    return a < b ? a = b, 1 : 0;
}

template<class T> void print(T a) {
    for (auto x : a) cout << x << " ";
    cout << el;
}

template<class T> void compress(T &a) {
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
}

const long long N = 1e5 + 27, inf = 2e18, bl = 320, base = 311, mod = 1e9 + 7, lim = 21;

struct Edge {
    ll u, v, w;
    Edge(){}
    Edge(ll _u, ll _v, ll _w) {
        u = _u, v = _v, w = _w;
    }
};

ll n, m, s, t, x, y, res = inf;
ll din[N], dout[N], d[N][3];
vector<pair<ll, ll>> adj[N];
vector<ll> dag[N];
Edge edge[2 * N];

void dijkstra(ll s, ll d[]) {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
    fu(i, 1, n) d[i] = inf;    
    d[s] = 0;
    q.push(make_pair(0, s));
    while (sz(q)) {
        ll u = q.top().ss, dist = q.top().ff;
        q.pop();
        if (dist > d[u]) continue;
        for (pair<ll, ll> tmp : adj[u]) {
            ll v = tmp.ff, w = tmp.ss;
            if (minimize(d[v], d[u] + w)) q.push(make_pair(d[v], v));
        }
    }
}

struct Info {
    ll u, dist, sta;
    Info(){}
    Info(ll _u, ll _dist, ll _sta) {
        u = _u, dist = _dist, sta = _sta;
    }
    bool operator < (const Info &other) const {
        return dist > other.dist;
    }
};

void go() {
    memset(d, 0x3f, sizeof(d));
    priority_queue<Info> q;
    q.push(Info(x, 0, 0));
    d[x][0] = 0;
    while (sz(q)) {
        ll u = q.top().u, dist = q.top().dist, sta = q.top().sta;
        q.pop();
        if (u == y) return void(minimize(res, dist));
        if (dist > d[u][sta]) continue;
        for (pair<ll, ll> tmp : adj[u]) {
            ll v = tmp.ff, w = tmp.ss;
            if (!sta) {
                if (minimize(d[v][0], dist + w)) q.push(Info(v, dist + w, 0));
            }
            else {
                if (minimize(d[v][2], dist + w)) q.push(Info(v, dist + w, 2));
            }
        }
        if (sta == 2) continue;
        for (ll v : dag[u]) if (minimize(d[v][1], dist)) q.push(Info(v, dist, 1));
    }
}

void back() {
    memset(d, 0x3f, sizeof(d));
    priority_queue<Info> q;
    q.push(Info(y, 0, 0));
    d[y][0] = 0;
    while (sz(q)) {
        ll u = q.top().u, dist = q.top().dist, sta = q.top().sta;
        q.pop();
        if (u == x) return void(minimize(res, dist));
        // cout << u << ' ' << dist << ' ' << sta << el;
        if (dist > d[u][sta]) continue;
        for (pair<ll, ll> tmp : adj[u]) {
            ll v = tmp.ff, w = tmp.ss;
            if (!sta) {
                if (minimize(d[v][0], dist + w)) q.push(Info(v, dist + w, 0));
            }
            else {
                if (minimize(d[v][2], dist + w)) q.push(Info(v, dist + w, 2));
            }
        }
        if (sta == 2) continue;
        for (ll v : dag[u]) {
            // cout << u << ' ' << v << el;
            if (minimize(d[v][1], dist)) q.push(Info(v, dist, 1));
        }
    }
}

signed main() {
    // freopen("bdbang.inp", "r", stdin);
    // freopen("bdbang.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t >> x >> y;
    fu(i, 1, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
        edge[i] = Edge(u, v, w);
    }
    dijkstra(s, din);
    dijkstra(t, dout);
    fu(i, 1, m) {
        ll u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (din[u] + w + dout[v] == din[t]) dag[u].push_back(v);   
        if (din[v] + w + dout[u] == din[t]) dag[v].push_back(u); 
    }
    go();
    back();
    cout << res;


}

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