(7.0 ĐIỂM) TỪ ĐỊA ĐIỂM A ĐẾN ĐỊA ĐIỂM B CÓ MỘT SỐ CON ĐƯỜNG ĐI, TRÊN M...

Bài 2: (7.0 điểm) Từ địa điểm A đến địa điểm B có một số con đường đi, trên mỗi

đường đi tốn một chi phí riêng, chi phí là một số nguyên từ 1 đến 9. Tương tự từ B đến

C, từ C đến D, … cũng vậy, xem hình minh họa sau:

2

7

1

Điểm

. . . .

4

A B C D E

cuối

5

Điểm đầu

3

6

Yêu cầu: Viết chương trình cho biết có bao nhiêu cách đi từ điểm đầu tiên đến điểm

cuối cùng (đường đi phải qua tất cả các điểm) và đi theo đường nào để tốn chi phí thấp

nhất.

- Dữ liệu vào: Nhập từ bàn phím một dòng văn bản cho biết các địa điểm và các số cho

biết chi phí tương ứng trên các đường đi giữa hai điểm đó. Ví dụ:

A2143B213C74D2756E nghĩa là có 5 địa điểm A,B,C,D,E và điểm cuối là E. Giữa A

Ví dụ:

Chuỗi nhập vào Xuất ra màn

hình Giải thích

A qua B có 4 cách, B qua C có 3 cách,

C qua D có 2 cách, D qua E có 4 cách

=> có 4*3*2*4=96 cách đi từ A đến E.

Từ A qua B có chi phí thấp nhất là 1

A2143B213C74D2756E 96

Từ B qua C có chi phí thấp nhất là 1

A1B1C4D2E

Từ C qua D có chi phí thấp nhất là 4

Từ D qua E có chi phí thấp nhất là 2