C-3BA y Las Rutas Incendiadas


Submit solution

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

Author:
Problem type
Allowed languages
C++, Python

El robot C-3BA, en su jornada por reparar robots en los confines de la Tierra, necesita ir desde una punta a otra de una isla del Caribe.

Existen n ciudades en la isla del Caribe, y hay m rutas bidireccionales entre ellas, la i-ésima ruta conecta las ciudades u_i y v_i, y tiene longitud w_i.

Se garantiza que un par de ciudades está conectada por a lo más una ruta, que ninguna ruta conecta una ciudad consigo misma y que se puede ir desde cualquier ciudad a cualquier otra siguiendo una secuencia de rutas.

C-3BA necesita ir desde la ciudad a la ciudad b, se garantiza que a y b son diferentes.

Recientemente, debido al cambio climático, alguna ruta podría incendiarse, no se puede pasar por una ruta incendiada.

A C-3BA le gustaría conocer, cuántas rutas x existen tal que, si la ruta x se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde a hasta b difiere con respecto a si no se hubiera incendiado ninguna ruta.

Note que la longitud del camino mínimo de a a b es igual a la menor suma de las longitudes de alguna secuencia de rutas que vaya desde a hasta b.

Subtareas

  • Subtarea 1 (10 puntos): m = n - 1 y la i-ésima ruta va de la ciudad i a la ciudad i+1 para todo 1 \leq i < n, n \leq 100 y w_i = 1 para todo i.

  • Subtarea 2 (20 puntos): m = n - 1, es decir, las rutas forman un árbol, n \leq 100 y w_i = 1 para todo i.

  • Subtarea 3 (20 puntos): n \leq 500, m \leq 1000.

  • Subtarea 4 (25 puntos): n \leq 500, m \leq 10000.

  • Subtarea 5 (25 puntos): Sin restricciones adicionales.

Entrada

En la primera línea de entrada, dos enteros n (2 \leq n \leq 10^5) y m (1 \leq m \leq 2\cdot 10^5), la cantidad de ciudades y rutas respectivamente.

En la segunda línea de entrada, dos enteros a y b, la ciudad de inicio y de final respectivamente.

En cada una de las siguientes m líneas, tres enteros u_i, v_i y w_i (1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq w_i \leq 10^9), indicando que existe una ruta bidireccional entre las ciudades u_i y v_i con longitud w_i.

Salida

Imprima un solo entero en una línea, la cantidad de rutas x tal que si x se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde a hasta b difiere con respecto a si no se hubiera incendiado ninguna ruta.

Ejemplo de Entrada

7 9
1 7
1 2 2
1 3 1
2 4 1
2 5 1
3 4 2
3 7 10
4 6 5
4 7 8
6 7 2

Ejemplo de Salida

2

Nota

Las rutas que si se incendian la longitud del camino mínimo de 1 a 7 aumenta son la ruta que va de la ciudad 4 a la 6 y la que va de la 6 a la 7.


Comments


  • 2
    josue  commented on April 9, 2023, 1:45 p.m.

    Nice problem