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

STRAVEL - Chuyến đi an toàn

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/stravel


Những con quỷ đã tràn vào quấy phá nông trang. Các tạo vật bẩn thỉu, xấu xí này đang cản trở những con bò mỗi khi một con đi từ nông trang (nằm tại bãi cỏ số 1) đến những cánh đồng khác. Con bò i sẽ đi từ nông trang đến cánh đồng i. Những con quỷ đã trở nên thông minh giống người. Chúng biết được đường đi ngắn nhất mà bò i thường đi để đến được cánh đồng i. Con quỷ i đợi bò i tại ở giữa con đường cuối cùng trong hành trình ngắn nhất của bò i đến bãi cỏ i, nhằm phá rối nó.

Dĩ nhiên là các con bò không muốn bị phá rối. Vì vậy, chúng chọn một lộ trình hơi khác để từ bãi cỏ 1 đến bãi cỏ i.

Tính thời gian tốt nhất để đi qua mỗi lộ trình mới và không phải ngắn nhất này sao cho bò i có thể tránh được quỷ i đang đợi nó ở con đường cuối cùng trong lộ trình ngắn nhất từ bãi cỏ 1 đến bãi cỏ i.

Có M con đường (2 <= M <= 200 000) được đánh số từ 1 đến M. Mỗi con đường là hai chiều và cho phép đi đến tất cả trong số N (3 <= N <= 100 000) bãi cỏ, được đánh số từ 1 đến N. Con đường i nối hai bãi cỏ là a_i (1 <= a_i <= N) và b_i (1 <= b_i <= N) và đòi hỏi thời gian t_i (1 <= t_i <= 1 000) để lại giữa hai đầu. Không có hai con đường nào nối cùng hai bãi cỏ, và không có con đường nào nối một bãi có với chính nó (a_i != b_i). Và thuận lợi hơn cả, lộ trình ngắn nhất mà mỗi con bò i thường đi đến bãi cỏ i là duy nhất trong mỗi test.

Dữ liệu

Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: N và M

Dòng 2...M+1: Dòng i+1 chứa 3 số nguyên: a_i, b_i và t_i

Dữ liệu mẫu
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Kết quả

Dòng 1...N-1: Dòng i ghi thời gian ngắn nhất để đi từ bãi cỏ 1 đến bãi cỏ i+1 sao cho tránh được việc đi qua con đường cuối cùng trong lộ trình ngắn nhất từ bãi cỏ 1 đến bãi cỏ i+1. Nếu không tồn tại một lộ trình như vậy, ghi -1 trên dòng đó.

Kết quả mẫu
3
3
6

Được gửi lên bởi:Jimmy
Ngày:2009-01-16
Thời gian chạy:0.600s
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:USACO January 2009 - Gold Division
Translated by khanhptnk

hide comments
2019-05-29 15:47:46
ve vinh uong hong tra den tu vi tri hiep hoang nghia
2015-12-12 09:53:40
-___________- xem sol nha xem sol nha
2015-07-12 08:38:06 there's no salvation for me...
.... 2 đứa chúng m bị trĩ à....
2015-07-07 15:30:04 Tran Thuy Luc
google thì chả dễ -_-
2015-07-06 12:50:27 Phong
de vai
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.