Submission #1092493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092493		fonikos01	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	305 ms	30720 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));
        }

        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> distU(N, INT64_MAX);
        vector<ll> distV(N, INT64_MAX);
        auto dijkstra = [&](ll u, vector<ll> &A)
        {
                pq.push(make_pair(0, u));
                while (!pq.empty())
                {
                        auto [cost, node] = pq.top();
                        pq.pop();
                        if (A[node] != INT64_MAX)
                                continue;
                        A[node] = cost;
                        for (auto [nei, c] : g[node])
                        {
                                pq.push(make_pair(cost + c, nei));
                        }
                }
        };
        dijkstra(u, distU);
        dijkstra(v, distV);

        vector<ll> dpU(N, INT64_MAX);
        vector<ll> dpV(N, INT64_MAX);
        for (int i = 0; i < N; i++) {
                dpU[i] = distU[i];
                dpV[i] = distV[i];
        }
        ll ans = distU[v];
        vector<ll> validNodes(N);
        vector<ll> indeg(N);
        vector<ll> st = {t};
        while (!st.empty()) {
                ll node = st.back();
                st.pop_back();
                validNodes[node] = 1;
                for (auto nei : nodePars[node]) {
                        indeg[nei]++;
                        if (validNodes[nei] == 0) continue;
                        validNodes[nei] = 1;
                        st.push_back(nei);
                }
        }
        validNodes.clear();
        validNodes.resize(N, 0);
        vector<ll> bfs = {t};
        while (!bfs.empty())
        {
                vector<ll> newbfs(0);
                for (auto node : bfs)
                {
                        ans = min(ans, dpU[node]+distV[node]);
                        ans = min(ans, dpV[node]+distU[node]);
                        validNodes[node] = 1;
                        for (auto par : nodePars[node])
                        {
                                dpU[par] = min(dpU[par], dpU[node]);
                                dpV[par] = min(dpV[par], dpV[node]);
                                indeg[par]--;
                                if (validNodes[par] || indeg[par] > 0)
                                        continue;
                                newbfs.push_back(par);
                        }
                }

                bfs = newbfs;
        }

        cout << ans << '\n';

        return 0;
}

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

        // ll caseCnt = 1;

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

        solve();

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

        return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'll solve()':
commuter_pass.cpp:93:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |                 auto [cost, node] = pq.top();
      |                      ^
commuter_pass.cpp:98:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |                 for (auto [nei, c] : g[node])
      |                           ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:119:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |                         auto [cost, node] = pq.top();
      |                              ^
commuter_pass.cpp:124:35: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |                         for (auto [nei, c] : g[node])
      |                                   ^

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