Submission #1092245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092245		fonikos01	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	880 ms	34112 KiB

commuter_pass

#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>

// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;

using namespace std;
const int LARGE = 1e9;

#define all(x) (x).begin(), (x).end()

using ll = long long;
typedef pair<ll, ll> pi;

// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
//         if (a.second < b.second)
//                 return true;
//         return false;
// }
// struct node
// {
//         // part which will store data
//         int data;
//         // pointer to the previous node
//         struct node *prev;
//         // pointer to the next node
//         struct node *next;
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// 	static const int mod = MOD;
// 	static constexpr mint rt() { return RT; } // primitive root
//  	int v; 
//  	explicit operator int() const { return v; } 
// 	mint():v(0) {}
// 	mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// 	mint& operator+=(mint o) { 
// 		if ((v += o.v) >= MOD) v -= MOD; 
// 		return *this; }
// 	mint& operator-=(mint o) { 
// 		if ((v -= o.v) < 0) v += MOD; 
// 		return *this; }
// 	mint& operator*=(mint o) { 
// 		v = int((ll)v*o.v%MOD); return *this; }
// 	friend mint pow(mint a, ll p) { assert(p >= 0);
// 		return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// 	friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// 	friend mint operator+(mint a, mint b) { return a += b; }
// 	friend mint operator-(mint a, mint b) { return a -= b; }
// 	friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

ll solve()
{
        ll N, M; cin >> N >> M;
        ll s, t; cin >> s >> t;s--;t--;
        ll u, v; cin >> u >> v;u--;v--;
        vector<vector<pair<ll,ll>>> g(N, vector<pair<ll,ll>>(0));
        for (int i = 0; i < M; i++) {
                ll a, b, c; cin >> a >> b >> c;a--;b--;
                g[a].push_back(make_pair(b, c));
                g[b].push_back(make_pair(a, c));
        }

        auto lol = [&](ll s, ll t, ll u, ll v) {
                vector<vector<ll>> nodePars(N, vector<ll>(0));
                vector<ll> vis(N);
                priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
                pq.push(make_pair(0, s));
                vector<ll> costToNode(N, INT64_MAX);
                while (!pq.empty()) {
                        auto [cost, node] = pq.top();
                        pq.pop();
                        if (costToNode[node] == -1) continue;
                        costToNode[node] = -1;
                        for (auto [nei, c] : g[node]) {
                                if (cost+c < costToNode[nei]) {
                                        costToNode[nei] = cost+c;
                                        nodePars[nei].clear();
                                        nodePars[nei].push_back(node);
                                } else if (cost+c == costToNode[nei]) nodePars[nei].push_back(node);
                                pq.push(make_pair(cost+c, nei));
                        }
                }
                vector<ll> validNodes(N);
                vector<ll> st = {t};
                while (!st.empty()) {
                        ll node = st.back();
                        st.pop_back();
                        validNodes[node] = 1;
                        for (auto par : nodePars[node]) {
                                if (validNodes[par]) continue;
                                st.push_back(par);
                        }
                }

                for (int i = 0; i < N; i++) {
                        if (validNodes[i] == 0) nodePars[i].clear();
                }

                auto sol = [&](ll u, ll v) {
                        vector<ll> spNodesToU(N, INT64_MAX);
                        pq.push(make_pair(0, u));
                        while (!pq.empty()) {
                                auto [cost, node] = pq.top();
                                pq.pop();
                                if (spNodesToU[node] != INT64_MAX) continue;
                                spNodesToU[node] = cost;
                                for (auto [nei, c] : g[node]) {
                                        pq.push(make_pair(cost+c, nei));
                                }
                        }

                        ll ans = INT64_MAX;
                        vis.clear();
                        vis.resize(N, 0);
                        pq.push(make_pair(0, v));
                        while (!pq.empty()) {
                                auto [cost, node] = pq.top();
                                pq.pop();
                                if (vis[node]) continue;
                                ans = min(ans, cost+spNodesToU[node]);
                                vis[node] = 1;
                                for (auto [nei, c] : g[node]) {
                                        pq.push(make_pair(cost+c, nei));
                                }
                                for (auto par : nodePars[node]) {
                                        pq.push(make_pair(cost, par));
                                }
                        }
                        
                        return ans;
                };

                return min(sol(u, v), sol(v, u));
        };
        cout << min(lol(s, t, u, v), lol(t, s, u, v)) << '\n';

	return 0;
}

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        // freopen("mootube.in", "r", stdin);
        // freopen("mootube.out", "w", stdout);

        // ll caseCnt = 1;


        // ll T;
        // cin >> T;
        // while (T--)
        // {
                
                solve();

                // 	cout << "Case #"<< caseCnt << ": " << ans << '\n';
                // 	caseCnt++;
        // }

        return 0;
}

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