#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <map>
using namespace std;
// Định nghĩa hằng số cho giá trị vô cùng lớn
const long long LL_INF = 4500000000000000000LL;
// Pair cho cạnh: {destination_node, weight}
typedef pair<int, int> Edge;
// Pair cho Dijkstra: {distance, node}
typedef pair<long long, int> State;
// Số lượng nút tối đa
const int MAXN = 100000;
int N, M, S, T, U, V;
vector<Edge> adj[MAXN];
// Mảng khoảng cách từ các nguồn khác nhau
long long distS[MAXN]; // Khoảng cách từ S
long long distU[MAXN]; // Khoảng cách từ U
long long distV[MAXN]; // Khoảng cách từ V
// Cấu trúc cho DAG của đường đi ngắn nhất từ S
vector<int> shortestPathParents[MAXN]; // Các nút cha trên đường đi ngắn nhất từ S
vector<int> shortestPathChildren[MAXN]; // Các nút con trong DAG (đảo ngược của parents)
bool reachableFromS[MAXN]; // Nút có nằm trên đường đi ngắn nhất từ S đến T không
// Hàm Dijkstra chung
void dijkstra(long long dist[], int source) {
fill(dist, dist + N, LL_INF);
dist[source] = 0;
// min_heap: {distance, node}
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, source});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (const auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
// Hàm Dijkstra đặc biệt để xây dựng DAG của đường đi ngắn nhất từ S
void dijkstraWithParentTracking(long long dist[], int source) {
fill(dist, dist + N, LL_INF);
dist[source] = 0;
for (int i = 0; i < N; ++i) {
shortestPathParents[i].clear();
}
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, source});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (const auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
long long newDist = dist[u] + weight;
if (newDist < dist[v]) {
dist[v] = newDist;
// Xóa cha cũ và thêm cha mới
shortestPathParents[v].clear();
shortestPathParents[v].push_back(u);
pq.push({dist[v], v});
} else if (newDist == dist[v]) {
// Thêm một cha khác có thể tạo đường đi ngắn nhất
shortestPathParents[v].push_back(u);
}
}
}
}
// Các mảng memoization cho Quy hoạch động
long long memoForward[MAXN]; // dpForward(i): min cost từ V đến bất kỳ nút nào từ i trở về T trong DAG
long long memoBackward[MAXN]; // dpBackward(i): min cost từ V đến bất kỳ nút nào trên đường đi S -> i trong DAG
// DP 1: Min(distV[x]) cho x từ i đến T trong DAG
long long dpForward(int u) {
if (memoForward[u] != -1) return memoForward[u];
// Base case: chính nó
long long best = distV[u];
// Truy hồi: tìm min trong số các con trong DAG
for (int v : shortestPathChildren[u]) {
best = min(best, dpForward(v));
}
return memoForward[u] = best;
}
// DP 2: Min(distV[x]) cho x từ S đến i trong DAG
long long dpBackward(int u) {
if (memoBackward[u] != -1) return memoBackward[u];
// Base case: chính nó
long long best = distV[u];
// Truy hồi: tìm min trong số các cha trong DAG
for (int v : shortestPathParents[u]) {
best = min(best, dpBackward(v));
}
return memoBackward[u] = best;
}
void solve() {
// Đọc input
cin >> N >> M >> S >> T >> U >> V;
// Chuyển sang chỉ số 0
--S; --T; --U; --V;
for (int i = 0; i < M; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
adj[a].push_back({b, c});
adj[b].push_back({a, c}); // Đồ thị vô hướng
}
// 1. Tính khoảng cách từ U và V
dijkstra(distU, U);
dijkstra(distV, V);
// 2. Tính khoảng cách từ S và xây dựng DAG của đường đi ngắn nhất từ S
dijkstraWithParentTracking(distS, S);
// 3. Xây dựng mảng con trong DAG (shortestPathChildren) và xác định nút reachable
fill(memoForward, memoForward + N, -1);
fill(memoBackward, memoBackward + N, -1);
fill(reachableFromS, reachableFromS + N, false);
for (int i = 0; i < N; ++i) {
shortestPathChildren[i].clear();
}
// BFS ngược từ T để chỉ xét các nút nằm trên đường đi S -> T
queue<int> q;
if (distS[T] != LL_INF) { // Chỉ bắt đầu nếu T có thể truy cập được từ S
q.push(T);
}
while (!q.empty()) {
int u = q.front(); q.pop();
if (!reachableFromS[u]) {
reachableFromS[u] = true;
for (int v : shortestPathParents[u]) {
// v là cha của u trên đường đi ngắn nhất S -> T
shortestPathChildren[v].push_back(u);
q.push(v);
}
}
}
// 4. Tính toán kết quả
// Ứng viên 1: U -> V trực tiếp (nếu có)
long long min_cost = distU[V];
// Ứng viên 2: U -> i -> (trục trặc của V) -> T
// i là một nút trên DAG của đường đi ngắn nhất S->T
for (int i = 0; i < N; ++i) {
if (reachableFromS[i] && distU[i] != LL_INF) {
// Chi phí cho V là min(chi phí thoát sớm, chi phí thoát muộn)
// Chi phí thoát sớm (Backward): V đi đến một nút x trên đường S->i
// Chi phí thoát muộn (Forward): V đi đến một nút x trên đường i->T
long long cost_V = min(dpForward(i), dpBackward(i));
// Tổng chi phí: U đi đến i + chi phí V
min_cost = min(min_cost, distU[i] + cost_V);
}
}
// 5. In kết quả
cout << min_cost << endl;
}
int main() {
// Tối ưu hóa I/O
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |