Олимпиадный тренинг

Задача . B. Jzzhu и города


Задача

Темы: графы жадные алгоритмы кратчайшие пути *2000

Jzzhu — президент страны A. В его стране есть n городов, пронумерованных от 1 до n. Город 1 — столица A. Также есть m дорог, соединяющих города. По i-й дороге можно дойти из города ui в город vi (и наоборот), длина этой дороги равна xi. Более того, в стране есть k железнодорожных маршрутов. По i-му маршруту можно доехать от столицы страны до города si (и наоборот), длина этого маршрута равна yi.

Jzzhu не хочет зря растрачивать государственный бюджет, поэтому он хочет закрыть некоторые железнодорожные маршруты. Пожалуйста, посчитайте для Jzzhu, какое максимальное количество железнодорожных маршрутов можно закрыть, если требуется выполнить следующее условие: длина кратчайшего пути из каждого города в столицу не должна измениться.

Входные данные

В первой строке записано три целых числа, n, m, k (2 ≤ n ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105).

В каждой из следующих m строк записано три целых числа, ui, vi, xi (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ xi ≤ 109).

В каждой из следующих k строк записано два целых числа, si и yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109).

Гарантируется, что существует по крайней мере один путь из каждого города в столицу. Обратите внимание, что между двумя городами может быть несколько дорог. Также может быть несколько железнодорожных маршрутов, ведущих из одного и того же города в столицу.

Выходные данные

Выведите единственное целое число, обозначающее максимальное количество железнодорожных путей, которые можно закрыть.


Примеры
№Входные данныеВыходные данные
1 5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5 
2
2 2 2 3
1 2 2
2 1 3
2 1
2 2
2 3 
2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет