Power plant - MarisaOJ: Marisa Online Judge

HOME
PROBLEMSET
ROADMAP
COMPETITION
TOPIC
RANKING
GUIDE
MASHUP
ABOUT
CONTACT

A country can be represented as a graph of

$n$ vertices and

$m$ edges, each vertex is a city. The government wants to build

$k$ power plant. The

$i^{th}$ power plant is going to be built at city

$A_i$ and has the radius of

$R_i$ (cities having distance to

$A_i$ no more than

$R_i$ receive power from this plant). The government now wants to know how many cities have access to power. ### Input - The first line contains 3 integers

$n, m, k$ . - The next

$m$ lines, each line contains 2 integers

$u, v$ , there is an edge between

$u$ and

$v$ . - The next

$k$ lines,

$i^{th}$ line contains 2 integers

$A_i, R_i$ . ### Output - Print the number of cities having access to power. ### Constraints -

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

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

$6 5 2 1 2 1 3 3 4 3 5 2 6 1 1 6 2$

Output:

$4$

Multisource BFS / Dijkstra
	Rough ocean
	Restaurant
	Escape from... dolls 2
	Power plant
	Iceberg

Topic

Graph

Shortest path

Rating

1500

Solution (0)

Solution