Submission #1243856

#TimeUsernameProblemLanguageResultExecution timeMemory
1243856longggggCommuter Pass (JOI18_commuter_pass)C++20
15 / 100
2096 ms31988 KiB
#include <bits/stdc++.h> using namespace std; // ===== BITWISE ===== // #define MASK(i) (1LL << (i)) #define BIT(x, i) (1LL & ((x) >> (i))) #define ON(x, i) ((x) | MASK(i)) #define OFF(x, i) ((x) & ~MASK(i)) #define LASTBIT(mask) ((mask) & -(mask)) // ===== OTHER ===== // #define Longgggg ios_base::sync_with_stdio(0); cin.tie(0); #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 mod(x, k) ((((x) % (k)) + (k)) % (k)) #define all(x) begin(x), end(x) #define fi first #define se second #define ll long long #define endl '\n' // ===== FILE ===== // #define IN "A.in" #define OUT "A.out" #define DEBUG "debug.out" //==================// const ll INF = 1e18; const int mxN = 1e5 + 5; int N, M, S, T, U, V; vector<pair<int, int>> adj[mxN]; vector<tuple<int, int, int>> edges; vector<ll> dijkstra(int start) { vector<ll> dist(N + 1, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto &[v, cost] : adj[u]) { if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; pq.emplace(dist[v], v); } } } return dist; } ll run_dijkstra_with_pass(set<pair<int, int>> &pass_edges) { vector<ll> dist(N + 1, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; dist[U] = 0; pq.emplace(0, U); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto &[v, cost] : adj[u]) { int realCost = pass_edges.count({u, v}) ? 0 : cost; if (dist[v] > dist[u] + realCost) { dist[v] = dist[u] + realCost; pq.emplace(dist[v], v); } } } return dist[V]; } void solve() { cin >> N >> M; cin >> S >> T; cin >> U >> V; FOR(i, 1, M) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); edges.emplace_back(a, b, c); } auto distS = dijkstra(S); auto distT = dijkstra(T); ll distST = distS[T]; // Build subgraph with only shortest-path edges vector<vector<pair<int, int>>> spG(N + 1); for (auto &[u, v, c] : edges) { if (distS[u] + c + distT[v] == distST) spG[u].emplace_back(v, c); if (distS[v] + c + distT[u] == distST) spG[v].emplace_back(u, c); } // Use DFS to trace multiple shortest paths from S → T const int LIMIT_PATHS = 500; vector<vector<int>> paths; vector<int> path; function<void(int)> dfs = [&](int u) { if ((int)paths.size() >= LIMIT_PATHS) return; path.push_back(u); if (u == T) { paths.push_back(path); path.pop_back(); return; } for (auto &[v, _] : spG[u]) { dfs(v); } path.pop_back(); }; dfs(S); ll best = INF; for (auto &p : paths) { set<pair<int, int>> pass_edges; for (int i = 0; i + 1 < (int)p.size(); i++) { pass_edges.insert({p[i], p[i + 1]}); pass_edges.insert({p[i + 1], p[i]}); // bidirectional } best = min(best, run_dijkstra_with_pass(pass_edges)); } // Also test no-pass case auto distU = dijkstra(U); best = min(best, distU[V]); cout << best << endl; } signed main() { if (fopen(IN, "r")) { freopen(IN, "r", stdin); freopen(OUT, "w", stdout); freopen(DEBUG, "w", stderr); } Longgggg solve(); return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(DEBUG, "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...