4089 - Insurgency

Created by Humberto Díaz Suárez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 14000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

In the distant future, the world is a dark place. The government uses algorithms to monitor the populace and detect dissent in real time. Disharmony, as they call it, is swiftly punished.

We are the resistance, a group that seeks to end the abuse of algorithms for social control. We have contacted you today with an important task. Our members move around the city by using the public hover-train network. There are a number of stations connected to each other by hover-trains which are available on demand. That is, once you arrive at a station, you can immediately board a train to another connected station.

While the hover-trains are essential to our operations, they are also an extension of the state's surveillance system. The government watches and stops passengers for targeted searches. To reduce costs, they only monitor trains that are part of a shortest path between some pair of stations.

We want to exploit this weakness in the system to travel more safely. Please find the minimum time to move from one station to another after minimizing the number of monitored hover-trains that must be taken.
En un futuro lejano, el mundo es un lugar oscuro. El gobierno utiliza algoritmos para monitorear a la población y detectar disidentes en tiempo real. La falta de armonía, como lo llaman, es inmediatamente castigada.

Somos la resistencia, un grupo que busca acabar con el abuso de algoritmos para el control social. Lo hemos contactado hoy con una tarea importante. Nuestros miembros se desplazan por la ciudad utilizando la red pública de trenes flotantes. Hay varias estaciones conectadas entre sí mediante trenes flotantes que están disponibles bajo demanda. Es decir, una vez que llegue a una estación, puede abordar inmediatamente un tren a otra estación conectada.

Si bien los trenes flotantes son esenciales para nuestras operaciones, también son una extensión del sistema de vigilancia del estado. El gobierno vigila y detiene a los pasajeros para realizar búsquedas específicas. Para reducir los costos, solo monitorean los trenes que forman parte de un camino más corto entre un par de estaciones.

Queremos aprovechar esta debilidad en el sistema para viajar de manera más segura. Por favor, encuentre el tiempo mínimo para movernos de una estación a otra después de minimizar el número de trenes flotantes monitoreados que se deben tomar.
In the distant future, the world is a dark place. The government uses algorithms to monitor the populace and detect dissent in real time. Disharmony, as they call it, is swiftly punished.

We are the resistance, a group that seeks to end the abuse of algorithms for social control. We have contacted you today with an important task. Our members move around the city by using the public hover-train network. There are a number of stations connected to each other by hover-trains which are available on demand. That is, once you arrive at a station, you can immediately board a train to another connected station.

While the hover-trains are essential to our operations, they are also an extension of the state's surveillance system. The government watches and stops passengers for targeted searches. To reduce costs, they only monitor trains that are part of a shortest path between some pair of stations.

We want to exploit this weakness in the system to travel more safely. Please find the minimum time to move from one station to another after minimizing the number of monitored hover-trains that must be taken.

Input specification

The input will begin with a line containing two integers N (2 ≤ N ≤ 200) and M (1 ≤ M ≤ 104), separated by a space, indicating the number of stations and the number of hover-train connections, respectively. The stations will be numbered 1 through N. The following M lines will each contain three integers U, V, and W (1 ≤ U < V ≤ N, 1 ≤ W ≤ 104), with a space separating each pair of consecutive integers. These will indicate that there is a two-way hover-train connection between stations U and V, and that the train ride lasts W seconds. There will be at most one connection between any two stations.

Then there will be another line containing an integer Q (1 ≤ Q ≤ 105). The following Q lines will each contain a question in the form of two integers A and B (1 ≤ A < B ≤ N), separated by a space. This asks, what is the minimum time to travel from station A to station B after minimizing the number of monitored hover-trains taken?
La entrada comenzará con una línea que contiene dos enteros N (2 ≤ N ≤ 200) y M (1 ≤ M ≤ 104), separados por un espacio, que indica el número de estaciones y el número de conexiones de tren flotante, respectivamente. Las estaciones estarán numeradas del 1 al N. Las siguientes M líneas contendrán tres enteros U, V y W (1 ≤ U <V ≤ N, 1 ≤ W ≤ 104), con un espacio que separa cada par de enteros consecutivos. Esto indicará que hay una conexión de tren flotante de doble sentido entre las estaciones U y V, y que el viaje en tren dura W segundos. Habrá como máximo una conexión entre dos estaciones cualquiera.

Luego habrá otra línea que contiene un número entero Q (1 ≤ Q ≤ 105). Las siguientes Q líneas contendrán una pregunta en forma de dos enteros A y B (1 ≤ A < B ≤ N), separados por un espacio. Esto pregunta, ¿cuál es el tiempo mínimo para viajar de la estación A a la estación B después de minimizar el número de trenes flotantes monitoreados?
The input will begin with a line containing two integers N (2 ≤ N ≤ 200) and M (1 ≤ M ≤ 104), separated by a space, indicating the number of stations and the number of hover-train connections, respectively. The stations will be numbered 1 through N. The following M lines will each contain three integers U, V, and W (1 ≤ U < V ≤ N, 1 ≤ W ≤ 104), with a space separating each pair of consecutive integers. These will indicate that there is a two-way hover-train connection between stations U and V, and that the train ride lasts W seconds. There will be at most one connection between any two stations.

Then there will be another line containing an integer Q (1 ≤ Q ≤ 105). The following Q lines will each contain a question in the form of two integers A and B (1 ≤ A < B ≤ N), separated by a space. This asks, what is the minimum time to travel from station A to station B after minimizing the number of monitored hover-trains taken?

Output specification

For each question, output a line containing one integer: what is the minimum time to travel from station A to station B while minimizing the number of monitored hover-trains taken?

Priority should be given to avoiding monitored trains, then reducing travel time. Assume that switching trains in a station is instantaneous, and that there always exists some sequence of trains that connects any pair of stations.
Para cada pregunta, imprima una línea que contenga un número entero: ¿cuál es el tiempo mínimo para viajar de la estación A a la estación B mientras se minimiza el número de trenes flotantes monitoreados?

Se debe dar prioridad a evitar los trenes monitoreados, y luego a reducir el tiempo de viaje. Supongamos que el cambio de trenes en una estación es instantáneo, y que siempre existe una secuencia de trenes que conecta cualquier par de estaciones.
The input will begin with a line containing two integers N (2 ≤ N ≤ 200) and M (1 ≤ M ≤ 104), separated by a space, indicating the number of stations and the number of hover-train connections, respectively. The stations will be numbered 1 through N. The following M lines will each contain three integers U, V, and W (1 ≤ U < V ≤ N, 1 ≤ W ≤ 104), with a space separating each pair of consecutive integers. These will indicate that there is a two-way hover-train connection between stations U and V, and that the train ride lasts W seconds. There will be at most one connection between any two stations.

Then there will be another line containing an integer Q (1 ≤ Q ≤ 105). The following Q lines will each contain a question in the form of two integers A and B (1 ≤ A < B ≤ N), separated by a space. This asks, what is the minimum time to travel from station A to station B after minimizing the number of monitored hover-trains taken?

Sample input

4 5
1 2 30
1 3 20
1 4 40
2 3 100
3 4 100
3
1 3
1 4
2 4

Sample output

20
40
200

Hint(s)

For the first question, we would move from station 1 to station 3 through the 20-second train that connects them. Even though this route is monitored, there are no better options.

For the second question, we would move from station 1 to station 4 through the 40-second train that connects them. Again, this route is monitored and there are no unmonitored routes.

For the third question, we would move from station 2 to station 4 by riding the train from 2 to 3, then the train from 3 to 4. This route takes 200 seconds but has no monitored trains.
Para la primera pregunta, nos moveríamos de la estación 1 a la estación 3 a través del tren de 20 segundos que los conecta. Aunque esta ruta se supervisa, no hay mejores opciones.

Para la segunda pregunta, nos moveríamos de la estación 1 a la estación 4 a través del tren de 40 segundos que los conecta. Nuevamente, esta ruta es monitoreada y no hay rutas no monitoreadas.

Para la tercera pregunta, nos moveríamos de la estación 2 a la estación 4 tomando el tren de 2 a 3, luego el tren de 3 a 4. Esta ruta dura 200 segundos pero no tiene trenes monitoreados.
For the first question, we would move from station 1 to station 3 through the 20-second train that connects them. Even though this route is monitored, there are no better options.

For the second question, we would move from station 1 to station 4 through the 40-second train that connects them. Again, this route is monitored and there are no unmonitored routes.

For the third question, we would move from station 2 to station 4 by riding the train from 2 to 3, then the train from 3 to 4. This route takes 200 seconds but has no monitored trains.