제출 #1092225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092225		fonikos01	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	424 ms	33208 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> 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;
        };

        cout << min(sol(u, v), sol(v, u)) << '\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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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