Problem
Viết chương trình tìm khoảng cách trong đồ thị vô hướng có trọng số với độ dài các cạnh không âm, từ một đỉnh cho trước đến mọi đỉnh khác. Chương trình phải nhanh đối với các biểu đồ thưa thớt lớn.
Đầu vào
Dòng đầu tiên của nội dung nhập chứa số NUM — số lần chạy khác nhau của thuật toán Dijkstra (trên các đồ thị khác nhau). Tiếp theo là NUM khối, mỗi khối có cấu trúc như sau.
Dòng đầu tiên của khối chứa hai số N và M cách nhau bởi dấu cách — số đỉnh và số cạnh của đồ thị. Tiếp theo là M dòng, mỗi dòng chứa ba số nguyên được phân tách bằng dấu cách. Hai cái đầu tiên trong số chúng, nằm trong khoảng từ 0 đến N–1 mỗi cái, biểu thị các đầu của cạnh tương ứng, cái thứ ba — nằm trong khoảng từ 0 đến 20000 và biểu thị độ dài của cạnh này. Ngoài ra, ở dòng cuối cùng của khối, một số duy nhất từ 0 đến N–1 — đỉnh, khoảng cách mà bạn cần tìm kiếm.
Số lượng biểu đồ khác nhau trong một thử nghiệm NUM không không vượt quá 5. Số đỉnh không vượt quá 60000, các cạnh — 200000.
Dấu ấn
In ra đầu ra tiêu chuẩn (màn hình) NUM dòng, mỗi dòng chứa Ni các số được phân tách bằng dấu cách — khoảng cách từ đỉnh bắt đầu được chỉ định của đồ thị vô hướng có trọng số đến đỉnh thứ 0, 1, 2, v.v. của nó. các đỉnh (được phép thêm một khoảng trắng sau số cuối cùng). Nếu một số đỉnh không thể truy cập được từ đỉnh ban đầu đã chỉ định, hãy in số 2009000999 thay vì khoảng cách (đảm bảo rằng tất cả các khoảng cách thực đều nhỏ hơn).
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |