Editorial for Bedao Grand Contest 12 - MINDIST


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét chung: ta thấy số ~X~ trong hàm định nghĩa cost có thể bỏ đi và tăng trọng số các cạnh của đồ thị lên ~X~ đơn vị.

Subtask 1: ~1 \leq n, m \leq 10~

Sinh ra tất cả các đường đi có thể trên đồ thị.

Subtask 2: ~1 \leq n, m \leq 100~

Ta có ~f[i][a][b]~ là đường đi có cost nhỏ nhất bắt đầu từ đỉnh ~S~ đến đỉnh ~i~ trên đồ thị và có cạnh max là cạnh thứ ~a~, cạnh min là cạnh thứ ~b~. Xuất phát từ đỉnh ~S~ ta tính các giá trị ~f[i][a][b]~ có thể.

Subtask 3: ~m = n~

Như subtask2 tuy nhiên cặp giá trị ~a,b~ của mỗi đỉnh chỉ có nhiều nhất 2 cặp giá trị.

Subtask 4:

Ta có thể coi việc trừ max và cộng min như việc trừ đi 1 trọng số bất kì và cộng một trọng số bất kì. Nếu đó không phải max và min thì đường đi không bao giờ nhỏ nhất. Do vậy ta áp dụng trực tiếp được thuật toán dijkstra với ~disk[i][mask]~ là đường đi có cost nhỏ nhất từ ~S~ đến ~i~ và ~mask~ thể hiện việc cộng hay trừ chưa.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.