PDA

View Full Version : [Q] Duong di ngan nhat


sboy_ht
15-01-2003, 18:05
Sang nay, thay cho minh mot bai ve duong di ngan nhat, nhung kho qua! Ai biet thi giup minh nhe
De bai:
Alice va Jack muon di tu thanh pho thu 1 den thanh pho thu n, nhung chi co mot so tien nhat dinh. Hay tim lo trinh ngan voi voi so tien it nhat nho hon hoac bang so tien co truoc cua Alice va Jack
INPUT
- Dong thu nhat gom so k(k<=10000) la so tien ma Alice va Jack dang co
- Dong thu hai: so n(n<=100) , so thanh pho duoc danh dau tu 1 -> n
- Dong thu ba : so r(r<=10000), so con duong bac qua n thanh pho do
- R dong tiep theo gom cac so
++S: thanh pho dau
++D:thanh pho cuoi
++L:Do dai doan duong noi thanh pho S va thanh pho D (L<=100)
++T:So chi phi can de di tu thanh pho S den thanh pho D

OUTPUT
- Gom do dai doan duong di ngan nhat thoa dieu kien de bai da dua ra
Cam on rat nhieu!
hiensmart
16-01-2003, 16:45
Hê THT, mày chơi căng wa' dzậy, thầy cho bài dzề làm tết mà chưa chi giờ mày hỏi rồi, cần thì gửi mail cho tao, tao gửi bài của tao thử, đúng khoảng 60%
t_duong2002
17-01-2003, 12:48
xem tài liệu về giải thuật Distra... mà đọc!
hieugc
30-08-2004, 02:40
Sách của Thầy Bùi Việt Hà là số dzách!!!!!!!!!!!
FinderDev
30-08-2004, 22:32
Bài toán tìm đường đi nên xem qua sách các đề thi tin hoc Olympic 30-4 , chứ viết ra đây chí ít cũng phải hơn trăm dòng .
Teak
03-09-2004, 07:35
Dùng thuật toán disktra ( Đồ thị ), hix !
bichduyen_nt
06-09-2004, 04:56
cho nói thêm một câu là thuật toán disktra cũng hơi khó nuốt, và hơi tốn bộ nhớ một tý
JetMrDong
12-09-2004, 06:42
Bài này là coi trọng "tiền" chứ không phải là "đường" nên bạn chỉ cần dùng Dijsktra là được thôi.
Nhưng bài coi trọng "đường" xong rồi mới đến "tiền" thì hơi phiền đấy.
JetMrDong
12-09-2004, 06:44
To bichduyen_nt, Dijsktra là thuật toán tìm đường ngắn nhất trong đồ thị có trọng số không âm tốt nhất và cũng là tốn ít bộ nhớ nhất đó.