Tour du lịch giá rẻ

View as PDF
Submit solution
Points: 100.00 (partial)
Time limit: 3.0s
Memory limit: 1G
Input: stdin
Output: stdout
Author:
admin
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Có N thành phố đánh số từ 1 đến N, N <= 100. Giữa một số cặp thành phố có đường đi hai chiều nối trực tiếp. Cần chọn một tour du lịch đi qua ít nhất 3 thành phố khác nhau, mỗi thành phố đúng một lần trừ thành phố đầu tiên đi qua đúng hai lần (lần đầu tiên và lần cuối cùng) sao cho tổng chi phí của tour du lịch là ít nhất.

Dữ liệu vào:

Dòng đầu tiên ghi hai số nguyên N, M với M là số đoạn đường nối trực tiếp hai thành phố. Tiếp theo là M dòng, mỗi dòng ghi ba số nguyên dương u, v, w với ý nghĩa là có đường đi hai chiều trực tiép từ thành phố u đến thành phố v với chi phí w, w <= 10000. Chú ý rằng giữa hai thành phố có thể có nhiều đường nối trực tiếp.

Kết quả:

Dòng thứ nhất ghi 1/0 tuỳ theo có hay không có tour du lịch theo yêu cầu trên. Nếu dòng thứ nhất ghi số 1, dòng thứ hai ghi số C là tổng chi phí của tour được chọn, dòng thứ 3 ghi số k là số thành phố khác nhau trong tour, cuối cùng là k dòng, mỗi dòng ghi tên một thành phố theo trình tự lần lượt đi trong tour.

Ví dụ:
INPUT 1
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
OUTPUT 1
1
61
4
1
3
5
2
INPUT 2
4 3
1 2 10
1 3 20
1 4 30
OUTPUT 2
0

Comments

Please read the guidelines before commenting.


  • 0
    nguyencaodiep2b  commented on Feb. 22, 2023, 2:21 a.m.

    cho em xin ý tưởng


  • 0
    lalalala  commented on Jan. 20, 2022, 3:12 p.m.

    cho em xin 1 test chấm của bài này đc ko ạ? :>


  • 0
    HMD  commented on Dec. 23, 2020, 2:59 p.m.

    cô add test bài này đi cô :<


    • 0
      kieulqd  commented on Dec. 27, 2020, 11:08 a.m. ← edited

      Có test rồi em nha!


    • 0
      ldn694  commented on Dec. 24, 2020, 4:58 a.m.

      gk3 z