LQDOJ Contest #7 - Bài 5 - Con Đường Dài Nhất

View as PDF



Authors:
Problem type
Allowed languages
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Scala
Points: 1900 (p) Time limit: 1.0s Memory limit: 1G Input: LARGEST.INP Output: LARGEST.OUT

Sau khi trở nên giàu có và có dịp được nghỉ dài ngày, _minhduc quyết định sẽ tìm đường sang nhà "bạn gái cũ" của shiba nhằm làm chuyện ai cũng biết, đó chính là rủ cô ấy đi chơi...

Nơi _minhduc sống là một thành phố có thể coi là một đồ thị vô hướng với \(n\) đỉnh và \(m\) cạnh. Nhà của _minhduc ở vị trí đỉnh \(1\) và nhà cô "bạn gái cũ" của shiba ở vị trí đỉnh \(n\).

Hiện tại, thành phố của cậu ấy đang thi công xây dựng. Có tất cả \(k\) vị trí đã được di dời dân cư nhằm chuẩn bị cho quá trình xây thêm đường phố. Có thể nói tập đoàn của shiba ở thành phố này là rất lớn, vì vậy tiếng nói của _minhduc với vai trò là một Giám đốc điều hành cũng rất có trọng lượng. Cậu ấy có thể yêu cầu xây dựng thêm một con đường giữa hai đỉnh bất kì đã được di dời dân cư để xây dựng đường phố kia. Cậu ấy cũng có thể xây dựng một con đường đè lên con đường đã có. Mục đích của cậu ấy là tối đa hóa độ dài của đường đi ngắn nhất từ nhà _minhduc tới nhà bạn gái cũ của shiba để tránh để lại dấu vết. Bạn hãy giúp cầu ấy nhé.

Yêu cầu: Tính độ dài lớn nhất của đường đi ngắn nhất sau khi đã xây dựng thêm một con đường giữa nhà của _minhduc và "bạn gái cũ" của shiba.

Input

  • Dòng thứ nhất chứa số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
  • Dòng thứ hai chứa ba số nguyên dương \(n,m,k\) (\(1 \le n,m \le 2 \times 10^5, 2 \le k \le n\)).
  • Dòng thứ ba chứa \(k\) số nguyên dương phân biệt \(s_1, s_2,..., s_k\) (\(1 \le s_i \le n\)).
  • \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) thể hiện một cạnh của đồ thị (\(1 \le u,v \le n\)).
  • Dữ liệu đảm bảo luôn có đường đi từ \(1\) đến \(n\) ngay cả khi chưa thực hiện nối hai đỉnh đặc biệt.

Output

  • Một dòng chứa một số nguyên dương duy nhất là kết quả bài toán.

Scoring

  • Subtask \(1\) (\(15\%\) số điểm): \(k = 2\).
  • Subtask \(2\) (\(20\%\) số điểm): \(k = n\).
  • Subtask \(3\) (\(20\%\) số điểm): \(n \le 100\).
  • Subtask \(4\) (\(20\%\) số điểm): \(k \le 10^3\).
  • Subtask \(5\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

LARGEST.INP
1
7 6 2
4 6
1 2
2 3
3 4
4 5
5 6
6 7
LARGEST.OUT
5
Note


Ta nối hai đỉnh đặc biệt \(4\)\(6\). Lúc này độ dài đường đi ngắn nhất từ \(1\) tới \(7\)\(5\).


Comments

There are no comments at the moment.