| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243850 | longgggg | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define Longgggg ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define endl '\n'
#define fi first
#define se second
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 start, const vector<vector<pair<int, int>>>& g) {
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] : g[u]) {
if (dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
pq.emplace(dist[v], v);
}
}
}
return dist;
}
vector<vector<pair<int, int>>> shortest_path_graph(mxN);
vector<vector<int>> all_paths;
vector<int> current_path;
void dfs(int u, int t, vector<bool>& visited) {
if (u == t) {
all_paths.push_back(current_path);
return;
}
visited[u] = true;
for (auto &[v, id] : shortest_path_graph[u]) {
if (!visited[v]) {
current_path.push_back(id);
dfs(v, t, visited);
current_path.pop_back();
}
}
visited[u] = false;
}
void solve() {
cin >> N >> M;
cin >> S >> T;
cin >> U >> V;
edges.resize(M);
FOR(i, 0, M - 1) {
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
auto distS = dijkstra(S, adj);
auto distT = dijkstra(T, adj);
ll shortest = distS[T];
// Xây dựng đồ thị chỉ gồm các cạnh trên ít nhất 1 đường đi ngắn nhất
for (int i = 0; i < M; ++i) {
auto [a, b, c] = edges[i];
if (distS[a] + c + distT[b] == shortest || distS[b] + c + distT[a] == shortest) {
shortest_path_graph[a].emplace_back(b, i);
shortest_path_graph[b].emplace_back(a, i);
}
}
// Truy vết tất cả các đường đi từ S đến T bằng DFS
vector<bool> visited(N + 1, false);
dfs(S, T, visited);
ll ans = INF;
for (auto& path_ids : all_paths) {
// Tạo graph mới với commuter pass là các cạnh trên đường đi hiện tại
vector<vector<pair<int, int>>> newG(N + 1);
unordered_set<int> pass_edges(path_ids.begin(), path_ids.end());
for (int i = 0; i < M; ++i) {
auto [a, b, c] = edges[i];
int cost = (pass_edges.count(i) ? 0 : c);
newG[a].emplace_back(b, cost);
newG[b].emplace_back(a, cost);
}
auto d = dijkstra(U, newG);
ans = min(ans, d[V]);
}
cout << ans << endl;
}
int main() {
if (fopen("A.in", "r")) {
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
freopen("debug.out", "w", stderr);
}
Longgggg
solve();
return 0;
}