GAMES

Nguồn: Đề thi chọn học sinh giỏi Tin học tỉnh Khánh Hòa ngày 04/04/2017

Tý vừa mới khám phá ra một trò chơi trên mạng rất thú vị. Một trong những điều thú vị là người chơi phải nhập vai một người thám hiểm để đi tìm kho báu. Trò chơi mô phỏng một vùng biển trong đó có một quần thể gồm N hòn đảo được đánh số thứ tự từ 1 đến N. Trong quần thể các hòn đảo này có một hòn đảo đang chứa một kho báu có giá trị rất lớn, nhưng để vào được kho báu người chơi phải có chìa khóa để mở cửa kho báu. Giữa các hòn đảo này đã có M cây cầu bắc qua sao cho giữa hai hòn đảo chỉ có không quá một cây cầu bắc qua và từ một hòn đảo bất kỳ có thể đến được các đảo khác bằng con đường đi qua những cây cầu này. Khi đi qua mỗi cây cầu, người chơi phải bỏ ra một số tiền dùng để mua vé qua cầu. Chìa khóa để mở kho báu được treo ở giữa một cây cầu đặc biệt, khi đi qua cây cầu này, người chơi không cần phải mua vé nhưng để lấy được chìa khóa người chơi phải đi qua cầu đúng một lần duy nhất (không quay lại đầu cầu đã đi qua) vì sau khi lấy chìa khóa và qua khỏi cầu thì cầu sẽ bị sập.

Yêu cầu: Trò chơi cho biết chỉ số hòn đảo ban đầu khi người chơi xuất phát, vị trí cây cầu có treo chìa khóa và chỉ số của hòn đảo chứa kho báu, bạn hãy lập trình tính xem Tý có thể chơi để lấy được chìa khóa và đến được kho báu để lấy châu báu hay không và nếu được thì phải tốn ít nhất bao nhiêu tiền để mua vé qua cầu.

Dữ liệu vào: Tệp văn bản GAMES.INP gồm:

+ Dòng đầu ghi số nguyên N và M (2 ≤ N ≤ 1000, N ≤ M ≤ N(N-1)/2);

+ Dòng thứ hai ghi 4 số nguyên s, t, a và b, trong đó s là thứ tự hòn đảo xuất phát của người chơi, t là chỉ số hòn đảo chứa kho báu và a, b (a ≠ b) là số thứ tự của hai hòn đảo có cây cầu bắc qua đang giữ chìa khóa mở kho báu.

+ Dòng thứ i (i =1..M) trong M dòng tiếp theo ghi 3 số nguyên u_i, v_i, z_i với ý nghĩa là có cây cầu bắc từ đảo có chỉ số u_i đến đảo có chỉ số v_i (1≤ u_i, v_i, ≤ N, u_i ≠ v_i,) và phải mua vé với số tiền z_i là số nguyên (0<z_i ≤ 1000).

Kết quả: Ghi ra tệp văn bản GAMES.OUT tổng số tiền ít nhất mà người chơi phải chi phí để đi từ s qua cầu (a, b) để lấy chìa khóa và cuối cùng đến t để lấy kho báu. Nếu người chơi không thể thực hiện được thì chỉ ghi số -1.

Ví dụ:

GAMES.INP	GAMES.OUT		GAMES.INP	GAMES.OUT
6 6 1 6 4 5 1 2 5 1 3 2 2 3 1 2 4 2 3 4 4 5 6 8	13		6 6 1 4 4 5 1 2 5 1 3 2 2 3 1 2 4 2 3 4 4 5 6 8	-1

Test - code (FP) -  code (C++) - solution - đề (word)