Expert-itinérant – Qualification 2015

É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 A → B.

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 D_i et d’arrivée A_i de la i-ème rue, ainsi que le temps T_i 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 d_i et d’arrivée a_i 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 ≤ D_i ≤ N ;
• 1 ≤ A_i ≤ N ;
• 1 ≤ T_i ≤ 100 000 ;
• 1 ≤ d_i ≤ N ;
• 1 ≤ a_i ≤ N.