Tình yêu lạc lối 2

View as PDF

Submit solution


Points: 500
Time limit: 0.02s
Memory limit: 512M

Authors:
Problem type

nbkfucs và Bình Minh là đôi vợ chồng chưa cưới nhưng yêu nhau hết mực. Một hôm, quái vật Thuỳ Duyên đến và bắt Bình Minh đi. nbkfucs rất buồn và quyết định lên đường giải cứu. nbkfucs đến gặp thần huỷ diệt phuoc để cầu xin thần ban cho sức mạnh để giải cứu người yêu. Vì không biết quái vật có sức mạnh như thế nào nên nbkfucs đến gặp vị thần tối cao nhất là nguyendanghau2006 để tư vấn. Sau đó, nguyendanghau2006 đã ban cho nbkfucs một khả năng có thể nhìn thấy được dấu vết mà quái vật Thuỳ Duyên đã bay qua. Với sức mạnh mà nbkfucs được vị thần huỷ diệt phuoc ban cho thì nbkfucs có thể bay với một tốc độ chóng mặt để tới hang ổ của quái vật Thuỳ Diên. Nhưng trong lúc bay tới nơi thì nbkfucs gặp rắc rối khác. Hang ổ của con quái vật Thuỳ Diên là một mê cung có rất nhiều con đường, mà nbkfucs không thể vừa đi vừa tìm kiếm vì người yêu của anh sắp bị quái vật ăn thịt. nbkfucs đang không biết làm thế nào thì chợt nhớ ra các chúa tể coder trên lqđ, vì vậy nbkfucs quyết định nhờ các bạn tìm giúp con đường từ nơi anh đang đứng tới nơi người yêu đang bị bắt giữ sao cho độ ám ảnh và độ dài đường đi nhỏ nhất có thể.

Input

  • Dòng thứ nhất là 2 số \(n, m, s, t\) lần lượt là số phòng, số con đường, nơi-xuất phát và nơi cần đến. \((n,m \le 50, s,t \le n)\)
  • \(m\) dòng tiếp theo, mỗi dòng chứa 2 số u, v, w thể hiện đường nối giữa các phòng và độ ám ảnh của các con đường đó. \((w\le 10^9, u,v\le n)\)

Output

  • Dòng thứ nhất xuất ra độ ám ảnh nhỏ nhất có thể. Dòng thứ hai xuất ra con đường đi tìm được có độ ám ảnh và độ dài đường đi nhỏ nhất có thể. Nếu có nhiều phương án thì xuất nhiều nhất có thể. Nếu không tìm được đường đi thì xuất ra nbkfucs co don.

Sample input

5 7 1 5
1 2 1
1 4 1
1 5 2
2 3 1
2 5 1
3 4 1
4 5 1

Sample output

2
1 5

Sample output

5 4 1 5
1 2 1
1 4 1
3 4 1
2 3 1

Sample output

nbkfucs co don