Festival 1 - MarisaOJ: Marisa Online Judge

The Human Village can be represented by a connected graph with

$n$ locations and

$m$ connections. Reimu wants to organize a festival at location

$n$ instead of the Hakurei Shrine as usual. There are

$k$ people who want to attend the festival, and person number

$i$ is currently at location

$p_i$ . For each person, calculate the shortest path for them to reach the festival location. ### Input - The first line contains three integers

$n$ ,

$m$ , and

$k$ . - The second line contains

$k$ integers

$p_i$ . - The next

$m$ lines each contain two integers

$u$ and

$v$ , representing an edge between vertices

$u$ and

$v$ . ### Output - Print the length of the shortest path from vertex

$1$ to vertex

$n$ . ### Constraints -

$1 \le n, m, k \le 10^5$ . -

$1 \le u, v, p_i \le n$ . ### Example Input:

$4 4 3 2 3 4 1 2 2 3 3 4 4 1$

Output:

$2 1 0$

BFS / DFS
	Connected component
	Shortest path
	Finding the path
	Path on binary matrix
	Garden
	Operations on number
	Bipartite graph
	Tom and Jerry
	Festival 1
	Bamboo Forest of the Lost
	Radar
	Festival 2
	Go
	Escape from... dolls
	Long leg
	Lexicographically smallest path
	Graph coloring

Topic

Graph

Shortest path

Rating

1000

Solution (0)

Solution