Submission #1235053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235053		timeflew	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	334 ms	26808 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

#ifdef debug
#define dbg(...) cerr<<#__VA_ARGS__<<" = ", de(__VA_ARGS__)
template<typename T>
void de(T t) {cerr<<t<<endl;}
template<typename T, typename ...U>
void de(T t, U...u) {cerr<<t<<", ", de(u...);}
#else
#define dbg(...)
#define endl "\n"
#endif

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

const int mxN=1e5;

vector<pair<ll, ll>> adj[mxN];
vector<ll> s, t, u, v;
ll ans, dp[mxN], dp1[mxN];
int S, T, U, V; 

vector<ll> dij(int x) {
    vector<ll> dist(mxN, 1e18);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, x});
    dist[x]=0;
    while(pq.size()) {
        auto [dis, y]=pq.top();
        pq.pop();
        if(dis>dist[y]) continue;
        for(auto [z, w] : adj[y]) {
            if(dis+w<dist[z]) {
                dist[z]=dis+w;
                pq.push({dist[z], z});
            }
        }
    }
    return dist;
}

void dfs(int x) {
    if(dp[x]==-1) {
        dp[x]=1e18;
        for(auto [y, w] : adj[x]) {
            if(s[x]+t[x]==s[T]) {
                if(s[x]+w==s[y]) {
                    dp[x]=min(dp[x], v[x]);
                    dfs(y);
                    dp[x]=min(dp[x], dp[y]);
                    ans=min(ans, dp[x]+u[x]);   
                }
            } 
        }
    }
}

void dfs1(int x) {
    if(dp1[x]==-1) {
        dp1[x]=1e18;
        for(auto [y, w] : adj[x]) {
            if(s[x]+t[x]==s[T]) {
                if(s[x]+w==s[y]) {
                    dp1[x]=min(dp1[x], u[x]);
                    dfs1(y);
                    dp1[x]=min(dp1[x], dp1[y]);
                    ans=min(ans, dp1[x]+v[x]);
                }
            } 
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin>>n>>m;
    cin>>S>>T>>U>>V;
    --S, --T, --U, --V;
    for(int i=0; i<m; i++) {
        int a, b, c; cin>>a>>b>>c;
        --a, --b;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    s=dij(S);
    t=dij(T);
    u=dij(U);
    v=dij(V);
    ans=u[V];
    memset(dp, -1, sizeof(dp));
    memset(dp1, -1, sizeof(dp1));
    dfs(S);
    dfs1(S);
    cout<<ans;
    return 0;
}
//rating below 2700 must be solved orzorzorz

Compilation message (stderr)

commuter_pass.cpp: In function 'void usaco(std::string)':
commuter_pass.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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