C-3BA y Las Rutas Incendiadas
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 ciudades en la isla del Caribe, y hay rutas bidireccionales entre ellas, la -ésima ruta conecta las ciudades y , y tiene longitud .
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 la ciudad , se garantiza que y 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 existen tal que, si la ruta se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde hasta difiere con respecto a si no se hubiera incendiado ninguna ruta.
Note que la longitud del camino mínimo de a es igual a la menor suma de las longitudes de alguna secuencia de rutas que vaya desde hasta .
Subtareas
Subtarea 1 (10 puntos): y la -ésima ruta va de la ciudad a la ciudad para todo , y para todo .
Subtarea 2 (20 puntos): , es decir, las rutas forman un árbol, y para todo .
Subtarea 3 (20 puntos): , .
Subtarea 4 (25 puntos): , .
Subtarea 5 (25 puntos): Sin restricciones adicionales.
Entrada
En la primera línea de entrada, dos enteros y , la cantidad de ciudades y rutas respectivamente.
En la segunda línea de entrada, dos enteros y , la ciudad de inicio y de final respectivamente.
En cada una de las siguientes líneas, tres enteros , y , indicando que existe una ruta bidireccional entre las ciudades y con longitud .
Salida
Imprima un solo entero en una línea, la cantidad de rutas tal que si se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde hasta 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 a aumenta son la ruta que va de la ciudad a la y la que va de la a la .
Comments
Nice problem