Submission #453546

#	Time	Username	Problem	Language	Result	Execution time	Memory
453546		Karliver	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	660 ms	28704 KiB

commuter_pass

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<ll, ll> pairs;

const ll INF = 2e18;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}
ll du[N], dv[N], ds[N];
ll dp[N][3], ans = INF;
V<bool> vis(N, false);
VV<pairs> g(N);
ll n;

void Dx(ll st, ll d[]) {
    forn(i, n + 1) vis[i] = false;

    priority_queue<pairs> q;
    q.emplace(0, st);

    while(q.size()) {
        auto [s, v] = q.top();q.pop();

        if(!vis[v]) {
            d[v] = -s;
            vis[v] = 1;
            for(auto [c, w] : g[v]) q.push({s - w, c});
        }
    }

}


void Dy(ll st, ll e) {
    forn(i, n + 1) dp[i][0] = dp[i][1] = INF;

    forn(i, n + 1) vis[i] = false;
    using P = tuple<int, int, int>;
    priority_queue<P> q;
    q.emplace(0, st, 0);
    while(q.size()) {
        auto [s, v, par] = q.top();
        q.pop();

        if(!vis[v]) {
            ds[v] = -s;
            vis[v] = 1;
            dp[v][0] = min(du[v], dp[par][0]);
            dp[v][1] = min(dv[v], dp[par][1]);

            for(auto [c, w] : g[v]) q.emplace(s - w, c, v);
        }
        else if(-s == ds[v]) {
            if(min(du[v], dp[par][0]) + min(dv[v], dp[par][1]) <= dp[v][0] + dp[v][1]) {
                dp[v][0] = min(du[v], dp[par][0]);

                dp[v][1] = min(dv[v], dp[par][1]);
            }
        }
    }

    ckmi(ans, dp[e][0] + dp[e][1]);
}
            
    

void solve() {


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

    forn(i, m) {
        int a, b,c;
         cin >> a >> b >> c;
         g[a].push_back({b, c});
         g[b].push_back({a,c});
     }

     Dx(u, du);

     Dx(v, dv);

     ans = du[v];

     Dy(s, t);
     Dy(t, s);

     cout << ans << '\n';

}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dx(ll, ll*)':
commuter_pass.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [s, v] = q.top();q.pop();
      |              ^
commuter_pass.cpp:47:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |             for(auto [c, w] : g[v]) q.push({s - w, c});
      |                      ^
commuter_pass.cpp: In function 'void Dy(ll, ll)':
commuter_pass.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto [s, v, par] = q.top();
      |              ^
commuter_pass.cpp:71:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |             for(auto [c, w] : g[v]) q.emplace(s - w, c, v);
      |                      ^

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