Submission #1078054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078054		TsotneSV	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	167 ms	25408 KiB

commuter_pass

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces

// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

void fileIO(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;

const int inf=1e9,MAXN=1e5+5; 
const ll INF=1e18; 
const ld pi = 3.14159265358979323846;

int n,m,s,t,u,v;
vpi g[MAXN]; vi adj[MAXN]; 
vector<ll> dU,dV,dp1,dp2; ll ans;

void dfs(int node) {

    dp1[node] = dU[node];
    dp2[node] = dV[node];

    for(int i : adj[node]) {

        if(dp1[i] == INF) dfs(i);

        dp1[node] = min(dp1[node],dp1[i]);
        dp2[node] = min(dp2[node],dp2[i]);

    }

    ans = min({ans,dU[node] + dp2[node],dV[node] + dp1[node]});

}

void solve(int tc = 0){
    cin>>n>>m>>s>>t>>u>>v;

    for(int i=0;i<m;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }

    vector<ll> d(n+1,INF); d[s] = 0; priority_queue<pll,vector<pll>,greater<pll>> q; q.push({0,s});

    while(q.size()) {

        auto [w,node] = q.top(); q.pop();

        if(w != d[node]) continue;

        for(auto [to,we] : g[node]) {

            if(d[to] > d[node] + we) {
                d[to] = d[node] + we;
                q.push({d[to],to});
            }

        }

    }

    for(int i=1;i<=n;i++) {
        for(auto [j,w] : g[i]) {
            if(d[i] == d[j] + w) adj[i].pb(j);
        }
    } 

    dU = vll(n+1,INF); dV = vll(n+1,INF); dU[u] = dV[v] = 0; q.push({0,u});

    while(q.size()) {

        auto [w,node] = q.top(); q.pop();

        if(w != dU[node]) continue;

        for(auto [to,we] : g[node]) {

            if(dU[to] > dU[node] + we) {
                dU[to] = dU[node] + we;
                q.push({dU[to],to});
            }

        }

    } q.push({0,v});

    while(q.size()) {

        auto [w,node] = q.top(); q.pop();

        if(w != dV[node]) continue;

        for(auto [to,we] : g[node]) {

            if(dV[to] > dV[node] + we) {
                dV[to] = dV[node] + we;
                q.push({dV[to],to});
            }

        }

    } ans = dU[v];

    dp1 = dp2 = vll(n+1,INF);

    dfs(t);

    printl(ans);

}

signed main(){
  
    send help
  
    int tc=1;
    // cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

Compilation message (stderr)

commuter_pass.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
commuter_pass.cpp: In function 'void fileIO(std::string)':
commuter_pass.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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