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.