Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PCYCLE - Exploring the maze

Thám hiểm mê cung

Một mê cung gồm có N phòng và M hành lang nối các phòng, giữa hai phòng bất kì có không quá một hành lang nối chúng.
Một người muốn khám phá mê cung, anh ta sẽ xuất phát từ một phòng và đi dọc theo tất cả các hành lang sao cho mỗi hành lang được đi qua đúng một lần, rồi lại trở về vị trí xuất phát. Mỗi hành lang có một giá trị c cho biết khi đi qua nó thì năng lượng nhà thám hiểm sẽ cộng thêm với c (c có thể âm hay dương). Nhà thám hiểm bắt đầu xuất phát với năng lượng bằng 0, anh ta sẽ chết nếu sau khi đi hết một hành lang nào đó mà mức năng lượng nhỏ hơn 0.
Yêu cầu: Hãy giúp nhà thám hiểm tìm ra một hành trình an toàn thỏa mãn các yêu cầu đã đưa ra.

Dữ liệu

  • Dòng 1 là 2 số nguyên N, M. ( 1 ≤ N ≤ 200 )
  • M dòng tiếp theo, dòng thứ i gồm 3 số nguyên u, v, c cho biết có 1 hành lang nối phòng u với phòng v và giá trị năng lượng là c. ( |c| ≤ 10000 ) .

Kết quả

  • Nếu có không có hành trình nào an toàn thì ghi ra -1. Ngược lại ghi ra M+1 số nguyên là chỉ số phòng trên đường đi. Từ phòng xuất phát, qua các phòng, hành lang rồi quay trở về phòng xuất phát.

Ví dụ

Dữ liệu
3 3
1 2 2
1 3 -1
2 3 -1

Kết qủa
2 1 3 2

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2008-07-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Round 4
Problem Setter: Nguyễn Minh Hiếu

hide comments
2011-06-05 16:03:01 Noyethug
neu nhjeu dap an dung ghj ra dap an tuy y' a.???????????
2010-02-09 05:37:20 Nguyễn Trung Lợi
1 2 3 1 thì sao nhỉ ???
2009-08-01 15:09:12 Miko
sao bai nay no chua cho dieu kien lien thong ma em ko xet den truong hop ko lien thong ma van AC nhi?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.