//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Vận chuyển hàng

Bài 21:

Công ty MCA là một công ty vận tải nổi tiếng tại đất nước Peace, với mạng lưới hoạt động trong khắp cả nước. Sắp đến kỷ niệm 30 năm thành lập, giám đốc công ty quyết định mở một đợt khuyến mãi lớn cho tất cả các khách hàng. Cụ thể là công ty sẽ mở một số tuyến đường vận chuyển miễn phí cho khách hàng.

Mỗi tuyến đường như vậy sẽ xuất phát từ một thành phố, qua một số thành phố (không đi qua thành phố nào 2 lần) rồi quay về nơi xuất phát. Nếu tính chi phí vận chuyển trung bình trên từng tuyến đường thì chi phí chi ra cho đợt khuyến mãi này sẽ không nhỏ nên giám đốc cũng muốn các tuyến đường này thỏa điều kiện tổng độ dài đường đi chia cho tổng số con đường trong tuyến đường đó (gọi là chi phí của tuyết đường) là nhỏ nhất.

Cho một mạng lưới vận chuyển hàng của công ty MCA hãy tìm ra tuyến đường thích hợp nhất (thỏa cả 2 điều kiện trên) cho đợt khuyến mãi. Xuất ra chi phí của tuyến đường tìm được.

InputTRANS.INP

  • Dòng đầu tiên ghi hai số nguyên N và M là số thành phố và số con đường trong mạng lưới.
  • M dòng tiếp theo, mỗi dòng ghi ba số nguyên a b c với ý nghĩa có đường đi một chiều từ a đến b với độ dài là c.

Output:            TRANS.OUT

  • Dòng thứ nhất ghi một số thập phân với ít nhất 2 chữ số sau dấu phẩy là chi phí nhỏ nhất. Nếu không tồn tại tuyến đường nào thỏa mãn ghi ra -1.
  • Dòng thứ hai ghi số P là số lượng thành phố trên tuyến đường được chọn.
  • Dòng thứ ba ghi P + 1 số lần lượt là các thành phố trên tuyến đường được chọn.

Giới hạn:

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 9000
  • 1 ≤ c ≤ 223
  • Thời gian: 0.5 s/test
  • Bộ nhớ: 3MB

Ví dụ:

TRANS.INP TRANS.OUT
3 3

1 2 1

2 3 1

3 1 1

1.00

3

1 2 3 1

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 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 210,510 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: