Alex y su país

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Lua, Pascal, Python

En el país donde vive Alex hay n ciudades numeradas de \(1\) a \(n\). La ciudad \(1\) es la capital. También hay \(m\) carreteras bidireccionales conectando las ciudades. Alex sabe que el tamaño de la i-ésima carretera es \(xi\) y que esta conecta a las ciudades \(ui\) y \(vi\). Además en este país hay \(k\) rutas de trenes (bidireccionales), la i-ésima ruta conecta a la capital con la ciudad \(Si\) y el tamaño de esta ruta es \(yi\).

Alex quiere cerrar la mayor cantidad de rutas de trenes de tal forma que el tamaño del camino mínimo desde la capital hacia cualquier otra ciudad no cambie.

Note que al cerrar una ruta de tren esta no se puede seguir utilizando.

Formato de entrada:

La primera línea contiene tres enteros \(n,m,k (2<=n<=10^5;1<=m<=3*10^5;1<=k<=10^5)\).

Las siguientes \(m\) líneas contienen tres enteros \(ui,vi,xi (1<=ui,vi<=n;ui≠vi;1<=xi<=10^9)\).

Las siguientes \(k\) líneas contienen dos enteros \(si, yi (2<=si<=n;1<=yi<=10^9)\).

Se garantiza que se puede ir desde la capital hacia cualquier otra ciudad. Note que pueden haber múltiples carreteras entre un mismo par de ciudades, también note que pueden haber múltiples rutas de trenes desde la capital hacia una ciudad.

Formato de salida:

En una única línea imprima un entero representando la máxima cantidad de rutas de trenes que Alex puede cerrar.

Entrada #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

Salida #1

2

Entrada #2

2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

Salida #2

2

Comments

There are no comments at the moment.