Processing math: 97%
Solutions of Train pass - MarisaOJ: Marisa Online Judge

Solutions of Train pass

Select solution language

Write solution here.


User Avatar lftroq    Created at    13 likes

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 ST. 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 Tdsu+dtv+w=dst. Đường đi tối ưu là: XUVY, với UV2 đỉ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ứ 23. - Lớp thứ 23 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: XUS (hoặc T) V. Với UV 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>#defeendln#defefifirst#defesesecondusingnamespacestd;typedeflonglongll;constN=1e5+5;constllINF=1e15;n,m,s,t,x,y;r<pair<,graph[N],g[4N];lld[2][N],d1[4N];voijkstra(s,k){for(i=1;in;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