Submission #1127230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127230		guessme	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	318 ms	63088 KiB

commuter_pass

#include <bits/stdc++.h>
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())

using namespace std;
const int  N = 1e6+7;
const int M = 1e9+7;
const ll oo = 3e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r) {
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n, m, s, t, x, y;
vector <pair <int, int>> g[N];
ll ds[N], dt[N], dx[N], dy[N];
vector <int> adj[N];
ll f[N], rev_f[N];

void dij(int st, ll d[]) {
    priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <pair <ll, ll>>> q;
    for (int i = 1; i <= n; i++) {
        d[i] = oo;
    }
    d[st] = 0;
    q.push({0, st});
    while (q.size()) {
        auto k = q.top();
        q.pop();
        if (d[k.se] != k.fi) continue;
        for (auto [u, w]: g[k.se]) {
            if (d[u] > w + k.fi) {
                d[u] = w + k.fi;
                q.push({d[u], u});
            }
        }
    }
}

bool vis[N];

void dfs(int u, int par = -1) {
    vis[u] = 1;
    f[u] = dx[u];
    rev_f[u]= dy[u];
    for (int v: adj[u]) {
        if (!vis[v]) {
            dfs(v);
        }
        f[u] = min(f[u], f[v]);
        rev_f[u] = min(rev_f[u], rev_f[v]);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    #define TASK ""
    if (fopen (".inp", "r")) {
        freopen (".inp", "r", stdin);
        freopen (".out", "w", stdout);
    }
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    
    cin >> n >> m;
    cin >> s >> t >> x >> y;
    
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    dij(s, ds);
    dij(t, dt);
    dij(x, dx);
    dij(y, dy);
    
    for (int i = 1; i <= n; i++) {
        for (auto gg: g[i]) {
            if (ds[i] + gg.se + dt[gg.fi] == ds[t]) adj[i].push_back(gg.fi);
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i);
    }
    
    ll ans = oo;
    
    for (int i = 1; i <= n; i++) {
        ans = min({ans, dx[i] + rev_f[i], dy[i] + f[i]});
    }
    cout << ans << '\n';
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

Compilation message (stderr)

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

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