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

Bài tập huấn luyện: Trung tâm kinh tế

 

 

Theo thống kê cho biết mức độ tăng trưởng kinh tế của nước Peace trong năm 2006 rất đáng khả quan. Cả nước có tổng cộng N thành phố lớn nhỏ  được đánh số tuần tự từ 1 đến N phát triển khá đồng đều. Giữa N thành phố này là một mạng lưới gồm M đường đi hai chiều, mỗi tuyến đường nối 2 trong N thành phố sao cho không có 2 thành phố nào được nối bởi quá 1 tuyến đường. Trong N thành phố này thì thành phố 1 và thành phố N là 2 trung tâm kinh tế lớn nhất nước và hệ thống đường đảm bảo luôn có ít nhất một cách đi từ thành phố 1 đến thành phố N.

Tuy nhiên,cả 2 trung tâm này đều có dấu hiệu quá tải về mật độ dân số. Vì vậy, đức vua Peaceful quyết định chọn ra thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba. Thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ tầng. Nhưng trong thời gian sửa chữa ấy, phải bảo đảm đường đi ngắn nhất từ thành phố 1 đến thành phố N không bị thay đổi, nếu không nền kinh tế quốc gia sẽ bị trì trệ.

Vị trí và đường nối giữa N thành phố được mô tả như một đồ thị N đỉnh M cạnh. Hãy giúp nhà vua đếm số lượng thành phố có thể chọn làm trung tâm kinh tế thứ ba sao cho thành phố được chọn thỏa mãn các điều kiện ở trên.

InputCENTRE.INP

  • Dòng đầu tiên ghi 2 số nguyên dương N và M là số thành phố và số tuyến đường.
  • Dòng thứ i trong số M dòng tiếp theo ghi 3 số nguyên dương xi, yi và di với ý nghĩa tuyến đường thứ i có độ dài di và nối giữa 2 thành phố xi, yi.

Output:            CENTRE.OUT

  • Dòng đầu tiên ghi số tự nhiên S là số lượng các thành phố có thể chọn làm trung tâm kinh tế thứ ba.
  • S dòng tiếp theo, mỗi dòng ghi 1 số nguyên dương là số thứ tự của các thành phố có thể chọn.

Giới hạn:

  • 2 ≤ N ≤ 30000
  • 1 ≤ M ≤ 100000
  • 1 ≤ di ≤ 1000
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB
  • Có 50% số test có N ≤ 100 và M ≤ 1000

Ví dụ:

CENTRE.INP CENTRE.OUT
6 6

1 2 1

2 3 1

3 6 1

1 4 100

4 5 100

5 6 100

2

4

5

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ê

  • 206,489 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: