3329 - Joutong-Travels

Created by Luis Manuel Díaz Barón
Added by luismo (2015-06-14)
Limits
Total Time: 25000 MS | Test Time: 2500 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Anders the Cat recently obtained his driver's license earlier this month. After some days of psychological and physical tests, Anders will work for an important Bus Company called Joutong-Travels. This company has a fleet of buses for traversing the whole city. The city where Anders currently lives has N stations connected by M bidirectional roads of arbitrary lengths in kilometers; each road connecting exactly two different stations. The stations are conveniently numbered from 1 to N. And the time to travel between two stations is equal to the sum of kilometers of the roads used to travel between the stations.

Joutong has assigned Anders to drive from station A to station Z, and he needs to do it in the shortest possible time since otherwise he would not get his full salary next month. Joutong has a GPS device installed in all their buses, which can show them all the shortest possible routes between any two stations in few seconds. Anders could take any route he wants to accomplish the task, but the time he spends must be equal to the minimal time to travel between those stations, initially provided to the company by the GPS service.

Peter the Mouse, the eternal enemy of Anders, is planning to put barriers on some roads to block or delay Anders' travel. Any road that has a barrier on it can no longer be traveled. Your task is to find how many barriers does Peter need to prevent Anders from reaching his destination on time (i.e. driving from station A to station Z in the minimum time) and getting his full salary?
Anders el Gato recientemente obtuvo su licencia de chofer a principios de este mes. Después de algunos días de las pruebas psicológicas y físicas, Anders va a trabajar para una importante empresa de autobuses llamada Joutong-Viajes. Esta empresa cuenta con una flota de autobuses para recorrer toda la ciudad. La ciudad donde vive Anders actualmente tiene N estaciones conectadas por M carreteras bidireccionales de longitudes arbitrarias en kilómetros; cada carretera conecta exactamente dos estaciones diferentes. Las estaciones están convenientemente numeradas de 1 a N. Y el tiempo para viajar entre dos estaciones es igual a la suma de kilómetros de las carreteras que se utilizan para viajar entre las estaciones.

Joutong ha asignado a Anders conducir desde la estación A hasta la estación Z, y él tiene que hacerlo en el menor tiempo posible, ya que de lo contrario no tendría su salario completo el próximo mes. Joutong tiene un dispositivo GPS instalado en todos sus autobuses, que les puede mostrar todas las rutas más cortas posibles entre dos estaciones y sólo toma unos pocos segundos. Anders puede tomar cualquier ruta que desee para llevar a cabo la tarea, pero el tiempo que utilice e ello debe ser igual al mínimo tiempo requerido para viajar entre las estaciones, proporcionado inicialmente a la empresa por el servicio GPS.

Pedro el Ratón, el eterno enemigo de Anders, está planeando poner barreras en algunas carreteras para bloquear o retrasar los viajes de Anders. Cualquier carretera que tenga una barrera en ella ya no puede ser recorrida. Su tarea es encontrar el número de barreras que Pedro necesita para evitar que Anders llegue a su destino a tiempo (es decir, la conducción desde la estación A a la Z en el tiempo mínimo) y conseguir su salario completo?
Anders the Cat recently obtained his driver's license earlier this month. After some days of psychological and physical tests, Anders will work for an important Bus Company called Joutong-Travels. This company has a fleet of buses for traversing the whole city. The city where Anders currently lives has N stations connected by M bidirectional roads of arbitrary lengths in kilometers; each road connecting exactly two different stations. The stations are conveniently numbered from 1 to N. And the time to travel between two stations is equal to the sum of kilometers of the roads used to travel between the stations.

Joutong has assigned Anders to drive from station A to station Z, and he needs to do it in the shortest possible time since otherwise he would not get his full salary next month. Joutong has a GPS device installed in all their buses, which can show them all the shortest possible routes between any two stations in few seconds. Anders could take any route he wants to accomplish the task, but the time he spends must be equal to the minimal time to travel between those stations, initially provided to the company by the GPS service.

Peter the Mouse, the eternal enemy of Anders, is planning to put barriers on some roads to block or delay Anders' travel. Any road that has a barrier on it can no longer be traveled. Your task is to find how many barriers does Peter need to prevent Anders from reaching his destination on time (i.e. driving from station A to station Z in the minimum time) and getting his full salary?

Input specification

In the first line, there are four space separated integers N (1 <= N <= 100), M (1 <= M <= 5000), A and Z (A != Z, 1 <= A, Z <= N). Each of the next M lines contains three space separated integers P, Q (P != Q, 1 <= P, Q <= N) and L (1 <= L <= 1000), meaning that there is a bidirectional road between stations P and Q and its length is L kilometers. You can safely assume that there exists at least one route between A and Z.
En la primera línea, hay cuatro números enteros separados por espacios N (1 <= N <= 100), M (1 <= M <= 5000), A y Z (A! = Z, 1 <= A, Z <= N). Cada una de las siguientes M líneas contiene tres enteros separados por espacios P, Q (P! = Q, 1 <= P, Q <= N) y L (1 <= L <= 1000), lo que significa que hay una carretera bidireccional entre las estaciones P y Q y su longitud es L kilómetros. Usted puede asumir con seguridad que existe al menos una ruta entre A y Z.
In the first line, there are four space separated integers N (1 <= N <= 100), M (1 <= M <= 5000), A and Z (A != Z, 1 <= A, Z <= N). Each of the next M lines contains three space separated integers P, Q (P != Q, 1 <= P, Q <= N) and L (1 <= L <= 1000), meaning that there is a bidirectional road between stations P and Q and its length is L kilometers. You can safely assume that there exists at least one route between A and Z.

Output specification

Output a line with an integer representing the minimum number of barriers to be set by Peter in order to complete his goal.
Usted debe imprimir una línea con un entero que representa el número mínimo de barreras que Pedro debe colocar con el fin de completar su meta.
In the first line, there are four space separated integers N (1 <= N <= 100), M (1 <= M <= 5000), A and Z (A != Z, 1 <= A, Z <= N). Each of the next M lines contains three space separated integers P, Q (P != Q, 1 <= P, Q <= N) and L (1 <= L <= 1000), meaning that there is a bidirectional road between stations P and Q and its length is L kilometers. You can safely assume that there exists at least one route between A and Z.

Sample input

6 10 1 4
1 2 4
2 3 2
3 4 1
4 5 5
5 6 4
1 3 6
2 4 3
1 5 2
4 6 1
1 2 4

Sample output

3

Hint(s)