Submission #1220311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220311		vuphuong	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	304 ms	28184 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 int ll
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
const ll INF = (ll)1e18;
const int MAXN = 100000 + 5;

int n, m, s, t, x, y;
vector<ii> g[MAXN];
vector<int> dag[MAXN];
int ds[MAXN], dt[MAXN], dx_[MAXN], dy[MAXN];
vector<iii> edges;
vector<char> inPath;

void djk(int st, int dist[]) {
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for(int i = 1; i <= n; i++) dist[i] = INF;
    dist[st] = 0;
    pq.push({0, st});
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto &e : g[u]) {
            int v = e.fi, w = e.se;
            if(dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// DFS to produce topo order on inPath subgraph
vector<int> topo;
vector<char> vis;
void dfs(int u) {
    vis[u] = 1;
    for(int v : dag[u]) {
        if(!inPath[v] || vis[v]) continue;
        dfs(v);
    }
    topo.pb(u);
}

int32_t 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 >> s >> t >> x >> y;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
        edges.pb({u, {v, w}});
    }
    // Compute shortest paths
    djk(s, ds);
    djk(t, dt);
    djk(x, dx_);
    djk(y, dy);
    ll D = ds[t];
    
    // Build DAG edges on shortest S->T paths
    inPath.assign(n+1, false);
    for(int i = 1; i <= n; i++) {
        if(ds[i] + dt[i] == D) inPath[i] = true;
    }
    for(auto &e : edges) {
        int u = e.fi, v = e.se.fi, w = e.se.se;
        if(inPath[u] && inPath[v] && ds[u] + w + dt[v] == D) dag[u].pb(v);
        if(inPath[v] && inPath[u] && ds[v] + w + dt[u] == D) dag[v].pb(u);
    }
    
    // DFS-based topo sort on inPath subgraph
    vis.assign(n+1, 0);
    topo.clear();
    for(int u = 1; u <= n; u++) {
        if(inPath[u] && !vis[u]) dfs(u);
    }
    reverse(topo.begin(), topo.end());

    // DP initialization
    vector<ll> dp(n+1, INF);
    ll ans = dx_[y];  // option: not use ticket
    for(int u : topo) dp[u] = dx_[u];

    // DP propagation on topo
    for(int u : topo) {
        ans = min(ans, dp[u] + dy[u]);
        for(int v : dag[u]) {
            // already ensured v in inPath
            dp[v] = min(dp[v], dp[u]);
        }
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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