Submission #911138

#	Time	Username	Problem	Language	Result	Execution time	Memory
911138		NoLove	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1238 ms	41524 KiB

commuter_pass

/**
 *    author : Lăng Trọng Đạt
 *    created: 17-01-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
const int MAXN = 1e5 + 5;
int du[MAXN], dv[MAXN]; // minimum distance from node u, v to other node
int ans = 0, n;
vector<pii> adj[MAXN];
 
void dijkstra1(int source, int* dist) {
    priority_queue<vi> pq; // {cost from source, node}
    pq.push({0, source});
    while (si(pq)) {
        vi x = pq.top(); pq.pop();
        if (dist[x[1]] == -1) {
            dist[x[1]] = -x[0];
            for (pii p : adj[x[1]]) {
                pq.push({x[0] - p.s, p.f});
            }
        }
    }
}
 
void dijkstra2(int from, int to) {
    vector<vi> nxt(n + 1), prv(n + 1); // DAG generate from dijkstra
    priority_queue<vi> pq; // {cost from source, node, prev_node}
    vi dist(n + 1, -1);
    vector<vi> dp(2, vi(n + 1, INF));
    pq.push({0, from, 0});
    while (si(pq)) {
        vi x = pq.top(); pq.pop();
        if (dist[x[1]] == -1) {
            dist[x[1]] = -x[0];
            dp[0][x[1]] = min(dp[0][x[2]], du[x[1]]);
            dp[1][x[1]] = min(dp[1][x[2]], dv[x[1]]);
            for (pii p : adj[x[1]]) {
                pq.push({x[0] - p.s, p.f, x[1]});
            }
        } else if (-x[0] == dist[x[1]]) {
            if (min(du[x[1]], dp[0][x[2]]) + min(dv[x[1]], dp[1][x[2]]) <= dp[0][x[1]] + dp[1][x[1]]) { 
                // This is to ensure that node which node u and node v have minimum distance will stand in one path
                // from node source to node x[1]
                dp[0][x[1]] = min(du[x[1]], dp[0][x[2]]);
                dp[1][x[1]] = min(dv[x[1]], dp[1][x[2]]);
            }
        }
    }
    mi(ans, dp[0][to] + dp[1][to]);
}
 
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 
 
    memset(du, -1, sizeof(du));
    memset(dv, -1, sizeof(dv));
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    int a, b, c;
    while (cin >> a >> b >> c) {
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
 
    dijkstra1(v, dv);
    dijkstra1(u, du);
    // FOR(i, 1, n) {
    //     db(i, du[i], dv[i]);
    // }
    ans = du[v];
 
    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
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("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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