Submission #1253203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253203		enxiayy	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	187 ms	27324 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using namespace std;
typedef long long ll;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 2e5 + 5;
const ll INF = 1e18;

int n, m;
int s, t, u, v;
vector < pair<int, ll> > adj[N];
ll distS[N], distT[N], distU[N], distV[N];
bool vis[N];
ll dpU[N], dpV[N];

void dijk(int st, ll dist[]) {
    priority_queue < pair<ll, int>, vector < pair<ll, int> >, greater < pair < ll, int> > > pq;
    for(int i = 1; i <= n; ++i) dist[i] = INF;
    dist[st] = 0;
    
    pq.push({0, st});
    while(!pq.empty()) {
        int u = pq.top().se;
        ll cost = pq.top().fi;
        pq.pop();
        if (cost > dist[u]) continue;

        for(auto s : adj[u]) {
            if (dist[s.fi] > dist[u] + s.se) {
                dist[s.fi] = dist[u] + s.se;
                pq.push({dist[s.fi], s.fi});
            }
        }
    }
}

ll ans = INF;

void f(int u) {
    vis[u] = 1;
    dpU[u] = dpV[u] = INF;
    for(auto s : adj[u]) {
        if (distS[u] + distT[s.fi] + s.se != distS[t]) continue;
        if (!vis[s.fi]) f(s.fi);
        dpU[u] = min(dpU[u], dpU[s.fi]);
        dpV[u] = min(dpV[u], dpV[s.fi]);
    }

    ans = min({ans, dpU[u] + distV[u], dpV[u] + distU[u]});

    dpU[u] = min(dpU[u], distU[u]);
    dpV[u] = min(dpV[u], distV[u]);
}

void solve() {
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    while(m--) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    dijk(s, distS);
    dijk(t, distT);
    dijk(u, distU);
    dijk(v, distV);
    f(s);
    ans = min(ans, distU[v]);
    cout << ans << el;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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