Submission #1014733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014733		daoda	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	287 ms	32016 KiB

commuter_pass

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

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(int x=a;x < int(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;

// template <class T>
// using Tree = 
    // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = ll(1e18) + 10;
const ll INIT = 7;
const ll MAX_VAL = 5000;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 1e5;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;

vi rd = {0, 1 , 0, -1}, cd = {1, 0, -1, 0};

ll add(ll a, ll b) {
    return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}

ll mult(ll a, ll b) {
    return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

ll dp[MAX_N + 1], ssp[MAX_N + 1], usp[MAX_N + 1], vsp[MAX_N + 1];
int khans[MAX_N + 1];
vpi adj[MAX_N + 1];
vector<vi> graph1(MAX_N + 1), graph2(MAX_N + 1), graph3(MAX_N + 1);
int n, m, s, t, u, v;

void djk(ll* sp, int strt, bool use_graph) {
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
    pq.push(make_pair(0, make_pair(strt, 0)));
    
    while(!pq.empty()) {
        auto [cost, nodes] = pq.top();
        auto [cur_node, prev_node] = nodes;

        pq.pop();

        if(use_graph && (sp[cur_node] == cost || !sp[cur_node]) && cur_node != strt) {
            graph1[cur_node].push_back(prev_node);
        }

        if((cur_node != strt && sp[cur_node]) || (cur_node == strt && cost)) continue;

        sp[cur_node] = cost;

        for(auto [next_cost, next_node] : adj[cur_node]) {
            pq.push(make_pair(cost + next_cost, make_pair(next_node, cur_node)));
        }
    }
}

ll solve(vector<vi>& graph, ll strt) {
    memset(khans, 0, sizeof(int) * (n + 1));

    FOR(i, 1, n + 1) {
        for(auto node : graph[i]) khans[node]++;
        dp[i] = usp[i];
    }

    ll ans = INF;
    queue<int> khans_list;
    khans_list.push(strt);

    while(khans_list.size()) {
        int cur = khans_list.front();
        khans_list.pop();

        ans = min(ans, dp[cur] + vsp[cur]);

        // cout << cur << " : " << dp[cur] << " " << vsp[cur] << endl;

        for(auto next : graph[cur]) {
            khans[next]--;
            dp[next] = min(dp[next], dp[cur]);
            if(!khans[next]) khans_list.push(next);
        }
    }

    // FOR(i, 1, n + 1) cout << dp[i] << " ";
    // cout << endl;

    return ans;
}

int main() { 

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    fast

    // TESTCASE {
        
    // }

    cin >> n >> m >> s >> t >> u >> v;

    FOR(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;

        adj[a].push_back(make_pair(c, b));
        adj[b].push_back(make_pair(c, a));
    }

    djk(usp, u, false);
    djk(vsp, v, false);
    djk(ssp, s, true);

    queue<int> tr;
    tr.push(t);

    while(tr.size()) {
        int cur = tr.front();
        tr.pop();

        for(auto next : graph1[cur]) {
            if(!graph2[next].size()) tr.push(next);
            graph2[next].push_back(cur);
            graph3[cur].push_back(next);
        }

        // cout << cur << " " ;
    }
    // cout << endl;

    cout << min(min(solve(graph3, t), solve(graph2, s)), usp[v]) << endl;

    // FOR(i, 1, n + 1) {
    //     cout << i << ": ";
    //     for(auto x : graph1[i]) cout << x << " ";
    //     cout << endl; 
    // }

    // FOR(i, 1, n + 1) cout << ssp[i] << " ";
    // cout << endl;
    // FOR(i, 1, n + 1) cout << usp[i] << " ";
    // cout << endl;
    // FOR(i, 1, n + 1) cout << vsp[i] << " ";
    // cout << endl;
}  

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