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.|

MECUNG - Mê cung

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274822/problem/J

              Trong một lần dạo chơi công viên BeeG, Nam phát hiện một trò chơi mới : mê cung. Mê cung gồm N phòng và M hành lang nối giữa các phòng. Mỗi hành lang nối 2 phòng u và v theo được sơn màu c. Bằng hành lang này người ta có thể đi từ phòng u sang phòng v và ngược lại.

           Một cuộc tỉ thí sắp được tổ chức. Những người tham gia sẽ bị bịt mắt và thả xuống căn phòng số 1 bằng trực thăng. Nhiệm vụ của người chơi là đến được căn phòng số N (phòng cuối cùng). Một thiết bị theo dõi sẽ được đeo vào mỗi người, ghi lại những căn phòng và hành lang mà người đó đi qua. Người sử dụng ít hành lang nhất để đến căn phòng N sẽ thắng cuộc. Nếu có nhiều người cùng sử dụng ít hành lang nhất, người có đường đi “đẹp” sẽ thắng. Một đường đi được xem là đẹp nếu dãy màu các hành lang mà người đó sử dụng liên tiếp có thứ tự từ điển nhỏ nhất trong tất các các đường đi ngắn nhất.

           Quyết tâm giành chiến thắng (vì phần thưởng cực kì hậu hĩnh), Nam thuê hẳn một máy bay trực thăng bay quay công viên BeeG và chụp hình mê cung từ phía trên. Hãy giúp Nam ghi lại đường đi lí tưởng nhất.

           Chú ý : Dãy (a1, a2, a3, … , ak) có thứ tự từ điển nhỏ hơn dãy (b1, b2, b3, … ,bk) nếu tồn tại một vị trí i nhỏ nhất (1 <= i <= k) sao cho ai<>bi thì aii.

                     Giữa hai phòng có thể có nhiều hơn một hành lang.

Input

            Dòng đầu gồm 2 số N, M – số phòng và số hành lang.
            M dòng sau, dòng i gồm 3 số ui  vi  ci thể hiện một hành lang.
            Giới hạn :        2 <= N <= 100000
                                 1 <= M <= 200000
                                 1 <= ui , vi <= N
                                 1 <= ci<= 109

            Có 33% số test có N <= 100.

Output

          Dòng đầu ghi K – độ dài đường đi ngắn nhất từ phòng 1 đến phòng N.
          Dòng thứ hai ghi K số là màu của K hành lang theo thứ tự được dùng để đi từ phòng 1 đến phòng N.

Example

Input:

4 6

1 3 2

3 4 3

1 2 1

2 4 4

3 1 1

2 3 1  Output:

2

1 3

Được gửi lên bởi:Alex & Friends
Ngày:2012-12-30
Thời gian chạy:0.5s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:by winterwolf94

hide comments
2017-10-09 16:57:24
ai <>b i rồi còn ai < bi :v
2017-09-19 15:31:20
97,14 :'(
2017-08-21 09:28:22 Ðặng Minh Tiến
https://kienthuc24h.com/mecung-spoj-me-cung/
2015-12-17 12:22:49 Lương Ðức Tuấn Ðạt
BeeG =))
2015-11-09 03:49:13 [CHV] Bác Thợ Sãn
tại sao dùng dijkstra lại không AC ?
TLE hay là WA :\
2015-08-21 10:26:52 .
Vl công viên BEEG.
2015-07-03 20:18:18
cái sự ảo diệu khi bạn sort sai vẫn ăn 77đ :v
2014-02-24 16:19:14 Nguyễn Anh Tuấn
dijkstra là ra nhưng mà bài ví dụ hình như sai thì phải
2013-12-15 15:07:54 Nguyễn Hoàng Nam
sao mình làm chỉ được có 40 điểm.thời mình dùng BFS+quicksort để tìm thứ tự từ điển nhỏ nhất. chắc ở đó nó bị quá thời gian
bạn nào ac rồi chỉ mình với ạ.!!!
2013-08-04 12:28:53 Ðộc cô cầu BUG
only BFS => AC :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.