Submission #707842

#	Time	Username	Problem	Language	Result	Execution time	Memory
707842		Alihan_8	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	293 ms	23184 KiB

commuter_pass

#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
bool chmin(int &x, int y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; cin >> n >> m;
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    --s, --t, --u, --v;
    vector <pair<int,int>> g[n];
    for ( int i = 1; i <= m; i++ ){
        int x, y, w; cin >> x >> y >> w;
        g[--x].pb({--y, w});
        g[y].pb({x, w});
    }
    const int inf = 1e17+1;
    auto F = [&](int st){
        vector <int> dis(n, inf);
        dis[st] = 0;
        priority_queue <pair<int,int>> q;
        q.push({0, st});
        while ( !q.empty() ){
            auto [val, cur] = q.top();
            q.pop(); val = -val;
            if ( val != dis[cur] ) continue;
            for ( auto [to, w]: g[cur] ){
                if ( chmin(dis[to], val+w) ){
                    q.push({-dis[to], to});
                }
            }
        }
        return dis;
    };
    auto S = F(s), T = F(t), U = F(u), V = F(v);
    vector <pair<int,int>> _list;
    for ( int i = 0; i < n; i++ ){
        if ( S[i]+T[i] == S[t] ){
            _list.pb({T[i], i});
        }
    }
    sort(all(_list), greater <pair<int,int>> ());
    vector <int> dpU(n, inf), dpV(n, inf);
    int Mn = U[v];
    for ( auto [val, it]: _list ){
        dpU[it] = U[it];
        dpV[it] = V[it];
        for ( auto [to, w]: g[it] ){
            if ( T[it]+w == T[to] ){
                chmin(dpU[it], dpU[to]);
                chmin(dpV[it], dpV[to]);
            }
        }
        chmin(Mn, dpU[it]+V[it]);
        chmin(Mn, dpV[it]+U[it]);
    }
    cout << Mn;

    cout << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void IO(std::string)':
commuter_pass.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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