Submission #722664

#	Time	Username	Problem	Language	Result	Execution time	Memory
722664		Cookie	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	384 ms	42780 KiB

commuter_pass

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 8e5 + 5;
vt<pll>adj[mxn + 1];
int n, m, s, t, u, v;
struct D{
    int s;
    ll d[mxn + 1];
    
   
    void go(int _s){
        forr(i, 1, n + 1){
            d[i] = 1e18;
        }
        s = _s; 
        priority_queue<pll, vt<pll>, greater<pll>>pq; 
        d[s] = 0; pq.push({d[s], s});
        while(!pq.empty()){
            auto [dd, u] = pq.top(); pq.pop();
            if(d[u] != dd)continue;
            for(auto [v, w]: adj[u]){
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w; 
                   
                    pq.push({d[v], v});
                }
        }   }
    }
    
};
D U, V;


ll res = 1e18;
struct D2{
    int s;
    ll d[mxn + 1], dp[2][mxn + 1];
    
 
    void go(int _s, int t){
        for(int i = 1; i <= n; i++){
            d[i] = dp[0][i] = dp[1][i] = 1e18;
        }
        s = _s; 
        priority_queue<pll, vt<pll>, greater<pll>>pq; 
        d[s] = 0; pq.push({d[s], s});
        dp[0][s] = U.d[s]; dp[1][s] = V.d[s];
        while(!pq.empty()){
            auto [dd, u] = pq.top(); pq.pop();
            if(d[u] != dd)continue;
            for(auto [v, w]: adj[u]){
                if(d[v] > d[u] + w){
                    dp[0][v] = min(dp[0][u], U.d[v]); dp[1][v] = min(dp[1][u], V.d[v]);
                    d[v] = d[u] + w; 
                    
                    pq.push({d[v], v});
                }else if(d[v] == d[u] + w){
                    if(min(dp[0][u], U.d[v]) + min(dp[1][u], V.d[v]) < dp[0][v] + dp[1][v]){
                        dp[0][v] = min(dp[0][u], U.d[v]); dp[1][v] = min(dp[1][u], V.d[v]);
                    }
                }
            }
        }
        res = min(res, dp[0][t] + dp[1][t]);
    }
    
};
D2 S, T;
signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    forr(i, 0, m){
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb(make_pair(b, w));
        adj[b].pb(make_pair(a, w));
    }
    U.go(u); V.go(v);
    res = U.d[v];
    S.go(s, t); T.go(t, s); 
    cout << res;
    return(0);
}

Compilation message (stderr)

commuter_pass.cpp: In member function 'void D::go(int)':
commuter_pass.cpp:37:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |             auto [dd, u] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:39:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |             for(auto [v, w]: adj[u]){
      |                      ^
commuter_pass.cpp: In member function 'void D2::go(int, int)':
commuter_pass.cpp:67:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |             auto [dd, u] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:69:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             for(auto [v, w]: adj[u]){
      |                      ^

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