Submission #1243847

#TimeUsernameProblemLanguageResultExecution timeMemory
1243847longggggCommuter Pass (JOI18_commuter_pass)C++20
0 / 100
2094 ms26224 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<tuple<int, int, int>> edges; vector<pair<int, int>> adj[mxN]; vector<ll> dijkstra(int src) { vector<ll> dist(N + 1, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; dist[src] = 0; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, c] : adj[u]) { if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pq.emplace(dist[v], v); } } } return dist; } void solve() { cin >> N >> M; cin >> S >> T; cin >> U >> V; FOR(i, 1, M) { int a, b, c; cin >> a >> b >> c; edges.emplace_back(a, b, c); adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } vector<ll> distS = dijkstra(S); vector<ll> distT = dijkstra(T); vector<ll> distU = dijkstra(U); ll best = INF; // Xét mỗi cạnh trên đường ngắn nhất từ S -> T for (auto &[a, b, c] : edges) { bool onPath = false; if (distS[a] + c + distT[b] == distS[T]) onPath = true; if (distS[b] + c + distT[a] == distS[T]) onPath = true; if (!onPath) continue; // Tạm thời tạo graph mới với commuter pass miễn phí cho cạnh (a, b) vector<vector<pair<int, int>>> newAdj(N + 1); for (auto &[x, y, w] : edges) { int cost = w; if ((x == a && y == b) || (x == b && y == a)) cost = 0; newAdj[x].emplace_back(y, cost); newAdj[y].emplace_back(x, cost); } // Dijkstra lại từ U trong graph mới 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] : newAdj[u]) { if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; pq.emplace(dist[v], v); } } } best = min(best, dist[V]); } // Ngoài ra, còn trường hợp không dùng commuter pass vector<ll> distNormal = dijkstra(U); best = min(best, distNormal[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:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         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...