Submission #909955

#	Time	Username	Problem	Language	Result	Execution time	Memory
909955		NoLove	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	1119 ms	41372 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);
    pq.push({0, from, 0});
    while (si(pq)) {
        vi x = pq.top(); pq.pop();
        if (dist[x[1]] == -1) {
            dist[x[1]] = -x[0];
            nxt[x[2]].pb(x[1]);
            prv[x[1]].pb(x[2]);
            for (pii p : adj[x[1]]) {
                pq.push({x[0] - p.s, p.f, x[1]});
            }
        } else if (-x[0] == dist[x[1]]) {
            nxt[x[2]].pb(x[1]);
            prv[x[1]].pb(x[2]);
        }
    }
    set<int> not_use; // set of node which is not part of any minimum part from node s to t 
    /// remove node from DAG to guranted that only node t have out_deg is 0
    vi in_deg(n + 1), out_deg(n + 1);
    vi q;
    FOR(i, 1, n) {
        if (si(nxt[i]) == 0 && i != to) q.pb(i);
        out_deg[i] = si(nxt[i]);
    }
    db(out_deg)
    db(prv)
    while (si(q)) {
        int x = q.back(); q.pop_back();
        not_use.insert(x);
        for (int u : prv[x]) {
            if (--out_deg[u] == 0) 
                q.pb(u);
        }
    }
    // db(out_deg)
    FOR(i, 1, n) {
        for (int u : nxt[i]) in_deg[u]++;
    }
    FOR(i, 1, n) {
        if (in_deg[i] == 0) q.pb(i);
        db(i, nxt[i])
    }
    db(not_use)
    // db(nxt)
    // using topological sort
    vi dp(n + 1, INF); // dp[i]: minimum from u to node i
    while (si(q)) {
        int x = q.back(); q.pop_back();
        if (not_use.count(x)) continue;
        mi(dp[x], du[x]);
        mi(ans, dv[x] + dp[x]);
        db(ans, x, dv[x], dp[x])
        for (int u : nxt[x]) {
            mi(dp[u], dp[x]);
            if (--in_deg[u] == 0) {
                q.push_back(u);
            }
        }
    }
}

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 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
commuter_pass.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i, 1, n) {
      |     ^~~
commuter_pass.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
commuter_pass.cpp:82:5: note: in expansion of macro 'FOR'
   82 |     FOR(i, 1, n) {
      |     ^~~
commuter_pass.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
commuter_pass.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     FOR(i, 1, n) {
      |     ^~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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