Expert-itinérant – Qualification 2015

Level 4

Énoncé

Pour répondre aux demandes d’itinéraires de ses utilisateurs, un célèbre logiciel de cartographie les relaie à des experts qui trouvent un trajet de durée minimale grâce à leur connaissance pointue de la ville.

Joseph Marchand, ayant obtenu le poste d’expert itinéraire par hasard, a maintenant besoin de votre aide pour ne pas se faire licencier. S’il est incapable de trouver son chemin, il dispose cependant d’une carte recensant les temps de trajet dans toutes les rues. Vous aurez donc accès aux données suivantes :

  • les différentes rues et les emplacements à leurs extrémités ;
  • le temps nécessaire pour aller d’un bout à l’autre de chaque rue. Attention, ce temps dépend du sens du parcours. De plus, si on vous indique le temps pour aller d’un point A à un point B, mais pas de B à A, cela signifie que la rue est à sens unique AB.

On vous donne un ensemble de requêtes à traiter urgemment ; trouvez, pour chacune d’entre elles, le temps minimum pour la satisfaire. Évidemment, il sera toujours possible de rejoindre l’arrivée depuis le départ.

Entrée

L’entrée comprendra :

  • sur la première ligne, 3 entiers séparés d’une espace : le nombre N d’emplacements différents, le nombre M de rues et le nombre R de requêtes ;
  • sur les M lignes suivantes, 3 entiers séparés d’une espace : les emplacements de départ Di et d’arrivée Ai de la i-ème rue, ainsi que le temps Ti nécessaire pour aller du départ à l’arrivée ;
  • sur les R lignes suivantes, 2 entiers séparés d’une espace : les emplacements de départ di et d’arrivée ai de la i-ème requête.

Sortie

Vous afficherez en sortie :

  • sur R lignes, le temps minimum nécessaire pour chaque requête.

Contraintes

  • 1 ≤ N ≤ 200 ;
  • 1 ≤ M ≤ 40 000 ;
  • 1 ≤ R ≤ 40 000 ;
  • 1 ≤ DiN ;
  • 1 ≤ AiN ;
  • 1 ≤ Ti ≤ 100 000 ;
  • 1 ≤ diN ;
  • 1 ≤ aiN.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
3 5 5
1 2 10
1 3 5
2 3 1
3 1 15
3 2 1
3 1
2 1
1 2
3 2
1 2
Sample output
15
16
6
1
6
Note

schema.png

Submit your solution

You have to register or log in to be able to submit your solution.