B. SMINPATH – Đường đi ngắn nhất (bản dễ)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài

Đề bài

Cho đồ thị vô hướng có trọng số G = (V, E, w) n đỉnh, m cạnh, cạnh (u, v) có trọng số w(u, v) và hai đỉnh s, t . Hãy tìm đường đi ngắn nhất từ s đến t .

Dữ liệu vào:

  • Dòng đầu chứa bốn số nguyên n, m, s, t là số đỉnh và số cạnh của G , đỉnh xuất phát và đỉnh đích;
  • m dòng tiếp theo, mỗi dòng chứa ba số số u, v, c cho biết một cạnh nối hai đỉnh u v trong G và trọng số c = w(u, v) tương ứng.

Dữ liệu ra:

  • Dòng đâu ghi số nguyên là độ dài đường đi ngắn nhất;
  • Dòng thứ hai ghi ra một đường đi từ s tới t có độ dài ngắn nhất.

Ví dụ:

Dữ liệu vào:
3 3 1 3
1 2 3
2 3 1
1 3 5
Dữ liệu ra:
4
1 2 3

Giới hạn:

  • 1 ≤ n ≤ 100; n - 1 ≤ m ≤ \frac{n(n – 1)}{2}; 0 ≤ c ≤ 10000 .