//
you're reading...
Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: Ăn quà vặt

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


Chọn đội tuyển dự thi quốc gia – 2015 – Bài 3


Đề bài


Bạn Tú năm nay dù đã học lớp 12 nhưng vẫn thích ăn quà vặt. Mỗi ngày, Tú phải đi từ nhà đến trường, đi từ trường đến trung tâm văn hóa để học đàn, đến nhà co học thêm, rồi học nhóm với các bạn,… Nói chung, Tú phải đến khá nhiều địa điểm. Trên mỗi đường đó, Tú phải qua các chặng đường có bán các món bánh ngọt mà Tú thích và vì thế nên bạn hết mua bánh ở chỗ này lại mua bánh ở nơi khác. Sau khi ăn uống theo sở thích này môt thời gian, Tú tăng cân khá nhiều và bạn ấy đang mong muốn hạn chế bớt lại. Tú đã quyết định là khi cần đi từ địa điểm này đến địa điểm khác, Tú sẽ chọn con đường đi mà tổng số tiền cần dùng là it nhất (nếu có nhiều đường như thế thì Tú muốn đi đường nào cũng được). Biết rằng mỗi đường đi có thể gồm một hoặc nhiều chặng đường, mỗi chặng đường lại nối với đúng hai địa điểm cho trước và trên chặng đường đó, có đúng môt cửa hàng bán món bánh ngọt mà Tú thích. Vị trí các cửa hàng và giá tiền là cố định nên để thuận lợi trong việc mua bánh, Tú muốn xác định xem với hai địa điểm bất kỳ, tổng số cửa hàng xuất hiện ở ít nhất một trong các con đường tiết kiệm nhất đi từ điểm nà đến điểm kia là bao nhiêu.

Yêu cầu. Cho trước số lượng địa điểm mà Tú phải đến hàng ngày, số lượng chặng đường đi trực tiếp giữa hai điểm, giá tiền của tiệm bánh trên mỗi chặng trong đó. Bạn hãy giúp Tú xác định xem để đi theo đường tiết kiệm nhất giữa hai địa điểm bất kì, tổng số tiệm bánh mà Tú có thể ghé thăm là bao nhiêu.

 

Dữ liệu vào. Trong file ANQUAVAT.INP, dòng đầu tiên có 2 số n,m chỉ số lượng địa điểm mà Tú phải đến và các con đường đi nối trực tiếp giữa chúng, 2 ≤ n ≤ 100,  0≤m≤. Trong m tiếp theo, mỗi dòng sẽ có 3 số nguyên dương x,y,z cho biết số thứ tự của điểm đầu, số thứ tự của điểm cuối của con đường và giá tiền tương ứng bán trên con đường đó với 1 ≤ x, y ≤ n, x<>y, 1 ≤ z ≤ 106. Mỗi cặp x, y như thế (không kể đến thứ tự) xuất hiện không quá một lần trong danh sách cặp địa điểm.

 

Dữ liệu ra. In vào file ANQUAVAT.OUT,  số nguyên c12,c13,c14,…,c1n,c23,c24,…,c2n,..,c(n-1)n theo thứ tự, trong đó cij, i<=i<j<=n là số cửa hàng mà Tú sẽ có khả năng viếng thăm khi đi từ địa điểm thứ i đến địa điểm thứ j. Trường hợp không có đường đi nào giữa hai địa điểm này thì số cửa hàng là 0.

 

Ví dụ

ANQUAVAT.INP ANQUAVAT.OUT
5 6

1 2 1

2 3 1

3 4 1

4 1 1

2 4 2

4 5 4

1 4 1 2 1 5 6 1 2 1

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 150,179 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: