Bài toán có thể được hiểu như sau: cho đồ thị vô hướng n đỉnh m cạnh có trọng số và các số nguyên S, T, X, Y. Ta có thể chọn 1 đường đi ngắn nhất bất kì từ S đến T và biến mọi trọng số trên đường này trở thành 0. Tìm chi phi nhỏ nhất có thể để đi từ đỉnh X đến đỉnh Y.
Trước hết, sử dụng thuật toán *dijkstra* cho 2 đỉnh S và T. Khi đó, ta có thể biết được trong m cạnh đã cho, cạnh nào thuộc đường đi ngắn nhất từ S đến T.
- dsi là đường đi ngắn nhất từ s đến i, tương tự với dti.
- Cạnh (u,v,w) (có hướng) thuộc đường đi ngắn nhất từ S đến T⇔dsu+dtv+w=dst.
Đường đi tối ưu là: X→U→V→Y, với U và V là 2 đỉnh thuộc **cùng 1 đường đi ngắn nhất** bất kì từ S đến T.
Ta sẽ xây dựng đồ thị bao gồm 4 lớp như sau:
- Lớp thứ 1 và lớp thứ 4: đồ thị ban đầu.
- Lớp thứ 2: đồ thị chỉ gồm các **cạnh 1 chiều thuộc ít nhất 1 đường đi ngắn nhất** từ S đến T, **trọng số cạnh là 0**.
- Lớp thứ 3: đồ thị chỉ gồm các **cạnh 1 chiều thuộc ít nhất 1 đường đi ngắn nhất** từ T đến S, **trọng số cạnh là 0**.
- Lớp thứ 1 sẽ có đường đi 1 chiều trọng số 0 đến lớp thứ 2 và 3.
- Lớp thứ 2 và 3 sẽ có đường đi 1 chiều trọng số 0 đến lớp thứ 4.
Lớp thứ 2 và lớp thứ 3 là **DAG**. Khi đó, bất kì cách di chuyển nào trên các lớp này sẽ ứng với tối đa 1 đường đi ngắn nhất từ S đến T.
Nếu ta không định hướng cho đường đi ngắn nhất, ta có thể sẽ gặp trường hợp này: X→U→S (hoặc T) →V. Với U và V thuộc 2 đường đi ngắn nhất từ S đến T khác nhau, không thỏa yêu cầu bài toán.
Tiếp tục áp dụng thuật toán *dijkstra* trên đồ thị vừa xây dựng, ta có được đáp án của bài toán.
Độ phức tạp thuật toán: Đồ thị mới sau khi dựng có thể có số đỉnh gấp 4 lần và số cạnh gấp 6 lần đồ thị ban đầu, thêm 2 lần dijkstra ban đầu, ta có thể coi là O(6mlog4n+2mlogn).
Ngoài ra, USACO Guide có lời giải khác cho bài toán này, độc giả có thể tham khảo [Tại đây](https://usaco.guide/problems/joi-2018commuter-pass/solution)
**Code mẫu:**
cpp=#∈clude<bitsstdc++.h>#def∈eendl′n′#def∈efifirst#def∈esesecondusingnamespacestd;typedeflonglongll;const∫N=1e5+5;constllINF=1e15;∫n,m,s,t,x,y;→→r<pair<∫,∫〉graph[N],g[4⋅N];lld[2][N],d1[4⋅N];voijkstra(∫s,∫k){for(∫i=1;i≤n;i++)d[k][i]=INF;d[k][s]=0;priorityqueue<pair<ll,pair<∫,∫〉,→→r<pair<ll,pair<∫,∫〉>,greater<pair<ll,pair<∫,∫〉〉pq;pq.push({d[k][s],{k,s}});whi≤((∫)pq.size()){lltemp=pq.⊤().fi;∫k=pq.⊤().se.fi,u=pq.⊤().se.se;pq.pop();if