Submission #1220313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220313		vuphuong	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	237 ms	24996 KiB

commuter_pass

/*ㅤ∧＿∧
　(　･∀･)
　(　つ┳⊃
ε (_)へ⌒ヽﾌ
 (　　(　･ω･)
 ◎―◎   ⊃  ⊃
BePhuongSuperSiuwi
From TK4 - CHT
ㅤㅤ／ ⌒＼____
　 /・　　 ）　　\
　/ノへ ノ　　　 /|
ノ　　  ＼\ |/_/_/*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define task "main"
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define ii pair<ll,ll>
const ll INF = LLONG_MAX;
const int MAXN = 100000 + 5;

int n, m;
int S, T, X, Y;
vector<ii> adj[MAXN];
vector<int> dag[MAXN];
ll ds[MAXN], dt[MAXN], dx_[MAXN], dy[MAXN];
vector<tuple<int,int,ll>> edges;
vector<char> inPath;

void dijkstra(int src, ll dist[]) {
    fill(dist + 1, dist + n + 1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto &e : adj[u]) {
            int v = e.fi;
            ll w = e.se;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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 <= n; i++) {
        adj[i].clear();
        dag[i].clear();
    }
    edges.clear();

    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edges.emplace_back(u, v, w);
    }

    // Compute shortest distances
    dijkstra(S, ds);
    dijkstra(T, dt);
    dijkstra(X, dx_);
    dijkstra(Y, dy);
    ll D = ds[T];

    // Mark nodes on any shortest S->T path
    inPath.assign(n+1, 0);
    for (int u = 1; u <= n; u++) {
        if (ds[u] + dt[u] == D) inPath[u] = 1;
    }

    // Build DAG of those edges
    for (auto &e : edges) {
        int u, v;
        ll w;
        tie(u, v, w) = e;
        if (inPath[u] && inPath[v]) {
            if (ds[u] + w + dt[v] == D) dag[u].pb(v);
            if (ds[v] + w + dt[u] == D) dag[v].pb(u);
        }
    }

    // Topo sort via Kahn
    vector<int> indegree(n+1, 0);
    for (int u = 1; u <= n; u++) if (inPath[u]) {
        for (int v : dag[u]) indegree[v]++;
    }
    queue<int> q;
    for (int u = 1; u <= n; u++) if (inPath[u] && indegree[u] == 0) q.push(u);
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.pb(u);
        for (int v : dag[u]) {
            if (--indegree[v] == 0) q.push(v);
        }
    }

    // DP
    vector<ll> dp(n+1, INF);
    ll ans = dx_[Y];  // not use ticket
    for (int u : topo) {
        dp[u] = dx_[u];
    }
    for (int u : topo) {
        ans = min(ans, dp[u] + dy[u]);
        for (int v : dag[u]) {
            dp[v] = min(dp[v], dp[u]);
        }
    }

    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

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

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