| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P18QPROG - QUALIFY ROUND 2018 G - ĐIỂM HẸN |
Ngày trở về quê hương, Tí rất muốn gặp mặt các bạn cũ của mình. Tại quê nhà, Tí có N người bạn, mỗi bạn lại sống ở một thị trấn khác nhau trong thành phố. Có M tuyến đường kết nối các thị trấn này với nhau. Tí muốn chọn một địa điểm gặp mặt tối ưu (điểm P) trên tuyến đường thứ K, sao cho giá trị lớn nhất độ dài quãng đường cần phải di chuyển của N bạn tới điểm P là nhỏ nhất.
Các bạn hãy giúp Tí tìm điểm P tối ưu nhất.
Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 10).
Mỗi test bắt đầu bởi 3 số nguyên N, M và K (2 ≤ N, M ≤ 100 000).
M dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c (c ≤ 10^9) cho biết có một tuyến đường 2 chiều kết nối thành phố u và v.
Input đảm bảo đơn đồ thị và không có tuyến đường nào tự kết nối thị trấn nào đó.
Output
Với mỗi test, in ra hai số thực X và Y với 5 chữ số sau dấu phảy, với X là khoảng cách giữa P và A, còn Y là giá trị lớn nhất của các đường đi ngắn nhất từ P tới các thị trấn 1, 2, …, N.
Thứ tự u, v của mỗi tuyến đường được giữ nguyên. Giả sử điểm P cần tìm kết nối thị trấn A và B. Khoảng cách giữa P và A bằng 8, P và B bằng 2, bạn phải in ra 8.
Nếu có nhiều đáp án, hãy tìm điểm P gần A nhất.
Example
Input: 2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5 Output: 5.00000 5.00000
2.00000 8.00000
Giải thích test 2: Điểm hẹn P nằm giữa thị trấn của hai bạn 1 và 2, cách thị trấn 1 khoảng cách bằng 2.
Khoảng cách bạn 1 phải di chuyển là 2.
Khoảng cách bạn 2 phải di chuyển là 8.
Khoảng cách bạn 3 phải di chuyển là 8.
Khoảng cách bạn 4 phải di chuyển là 7.
| Được gửi lên bởi: | adm |
| Ngày: | 2018-05-14 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
