#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... |