Hỏi bài : bài FPOLICE trên www.spoj.pl

https://www.spoj.pl/problems/FPOLICE/
Vì số đỉnh của đồ thị ít (max là 100) nên em dùng Floyd để tìm đường đi ngắn nhất cho dễ cài đặt:D
Mỗi lần sửa nhãn thì xét
- risk[u][v]>risk[u][w]+risk[w][v] && time[u][w]+timw[w][v]<=T thì sửa nhẵn risk[u][v] và sửa luôn time[u][v]
- risk[u][v]==risk[u][w]+risk[w][v], nếu time[u][v]>time[u][w]+time[w][v] thì sửa time[u][v]=time[u][w]+time[w][v]

bị WA, hok bị vì seo nữa, ý tưởng như vậy không biết có vấn đề gì không?

test thử cái này xem

Code:

1         
4   10      
0   1   9   11
1   0   7   11
9   7   0   2
11   11   2   0
0   100   1   1
100   0   1000   1
1   1   0   1
1   1   1   0

Output:
1101 10

(đi từ 1 --> 2 ---> 3 --> 4)

Mình nghĩ giải thuật này sẽ sai khi mà chọn theo công thức như vậy. Sẽ có trường hợp vì tối ưu risk bước trước mà bỏ qua một risk lớn hơn chút nhưng bước sau sẽ quá time, trong lúc đó risk lớn hơn bị bỏ qua nhưng thời gian chấp nhận được.

Bài này mình làm dùng mảng risk hai chiều d[i][time] đến i trong thời gian time rồi dùng dijkstra tìm đường đi ngắn nhất
https://www.spoj.pl/status/thanh_hung/

bài này có thể làm như sau:
Đầu tiên , sử dụng thuật toán floyd đề
1. Tìm độ lớn đường đi ngắn giữa 2 đỉnh bất kỳ
2. Tìm độ lớn thời gian đi nhỏ nhất giữa 2 đỉnh bất kỳ
Sau đó thực hiện vét cạn ( có đặt cận ) :
tại 1 đỉnh v nào đó , xét từng đỉnh i chưa đi qua , tính
temp1=tổng độ dài đường đi hiện tại + trọng số cạnh (v,i)
temp2=tổng thời gian đi hiện tại + thời gian đi giữa (v,i);
chỉ tiếp tục duyệt tiếp nếu (temp1+khoảng cách ngắn nhất giữa i -> n và temp2 + thời gian ngắn để từ i - > n <=t)
Tuy cách này có vẽ trâu bò nhưng chỉ mất 0.01s

Wow, vét cạn được 0.02s rùi:D
https://www.spoj.pl/status/FPOLICE,bt25/

Cách của Hùng có phải là QHĐ không vậy? Hùng có thể nói rõ hơn ko?

Cái này là tìm đường đi ngắn nhất, có điều mô hình lại "đỉnh" nên tạo ra mỗi đỉnh gồm 2 thông số, chỉ số đỉnh cũ và thời gian thôi, việc còn lại là tìm đường đi ngắn nhất trên tập đỉnh mới.

https://www.spoj.pl/status/FPOLICE,hcmut/

thanks bạn nào đã up code. thêm vô đây cho sau này ai muốn xem
hình như Thi code bài này dkg?

bài này cũng tương tự FPOLICE, anh em thịt nó luôn đi
http://vnoi.info/index.php?option=com_voj&task=viewStatement&problem=ROADS
http://www.spoj.pl/problems/ROADS/

hjxhjx, sao bai ben kia em chay co 0.01s thoi ma ben bai nay lai TLE