Le Conseil Galactique de Planification Hyperspatiale a pour mission, outre d'ordonner la destruction des planètes qui encombrent le passage, de choisir de manière cartésienne les lieux de construction des déviations hyperspatiales (autrement appelées voies express hyperspatiales).
Pour bien comprendre le système, il est nécessaire de présenter le système des routes spatiales :
- une route spatiale permet de relier deux points (deux planètes) de l'espace ;
- une route peut être prise dans les deux sens ;
- chaque route a un poids, qui dépend essentiellement de la distance qui sépare les deux points (ainsi que d'autres éléments comme la présence d'un pub qui sert du gargle blaster pan galactic sur le trajet) ;
- entre deux points il n'y a qu'une seule route directe (les déviations évoquées plus loin ne sont pas des routes à proprement parler, mais des trous de ver).
Prenons un exemple avec cinq planètes, appelées ici 1, 2, 3, 4 et 5 pour simplifier. La manière dont les routes sont reliées ainsi que les poids des routes est schématisé ainsi (dans le plan, donc les distance ne sont pas respectées) :
Sur ce schéma, on voit par exemple que la route qui relie les planètes 1 et 3 a pour poids 8. Il n'y a pas de route directe qui relie 1 et 5 (mais on peut aller de 1 à 5 en passant par 2, par 3 ou par 4).
Voyons maintenant quels sont les plus courts chemins (au sens des poids des routes) permettant de joindre toutes les paires de planètes :
- 1 à 2 : le poids est 8 qu'on fasse 1 > 2 directement ou 1 > 4 > 2
- 1 à 3 : le poids est 8
- 1 à 4 : le poids est 6
- 1 à 5 : le poids est 10 (en passant par 3)
- 2 à 3 : le poids est 2
- 2 à 4 : le poids est 2
- 2 à 5 : le poids est 3
- 3 à 4 : le poids est 4 (en passant par 2)
- 3 à 5 : le poids est 2
- 4 à 5 : le poids est 5 (en passant par 2)
On rappelle que les routes peuvent être prises dans les deux sens, inutile de compter la route de 2 à 1 si on a déjà compté la route de 1 à 2.
À présent, on peut noter l'efficacité du réseau routier en faisant la somme des poids des routes les plus courtes joignant chaque paire de planète. On obtient ici : 8 + 8 + 6 + 10 + 2 + 2 + 3 + 4 + 2 + 5 = 50. Le poids de ce réseau routier est 50.
L'objectif d'une déviation est de diminuer ce poids. Une déviation consiste à percer un trou de ver entre deux points (qui peuvent déjà ou non être reliés par une route, peu importe). Ce trou de ver pourra être emprunté, avec un poids de 0, puisqu'on pourra passer instantanément d'une des deux planètes à l'autre, ce qui changera les distances minimales entre plusieurs couples de planètes potentiellement.
Dans l'exemple qui précède, supposons qu'on mette une déviation hyperspatiale entre 1 et 4 :
Les poids seront alors les suivants :
- 1 à 2 : le poids est 2 (en passant par 4, et donc par la déviation 1 > 4)
- 1 à 3 : le poids est 4 (1 > 4 > 2 > 3)
- 1 à 4 : le poids est 0
- 1 à 5 : le poids est 5 (1 > 4 > 2 > 5)
- 2 à 3 : le poids est 2
- 2 à 4 : le poids est 2
- 2 à 5 : le poids est 3
- 3 à 4 : le poids est 4 (3 > 2 > 4)
- 3 à 5 : le poids est 2
- 4 à 5 : le poids est 5 (4 > 2 > 5)
Le poids du réseau routier avec la déviation hyperspatiale entre 1 et 4 est maintenant 29, ce qui est meilleur que 50 sans la déviation.
On pourrait plutôt placer la déviation entre 1 et 5 qui n'étaient pas reliés par une route, au lieu de mettre la déviation entre 1 et 4. Le résultat serait un peu meilleur encore avec un poids de 28.
La déviation pourrait aussi plutôt être placée entre 1 et 2 (il y a déjà une route entre 1 et 2). Dans ce cas, le poids du réseau routier serait 25, ce qui serait le mieux que l'on puisse faire. Par ailleurs, aucune autre déviation ne permet d'atteindre ce résultat de 25.
L'objectif du Bureau des Déviations du Conseil Galactique de Planification Hyperspatiale est de placer deux déviations dans un réseau routier contenant 45 planètes, décrit en entrée du problème.
La description est sous cette forme (ci-dessous, ce n'est qu'un exemple, pas les valeurs réelles) :
1, 2, 8
1, 3, 8
2, 5, 3
Cette description indique qu'il y a une route de 1 à 2 avec un poids de 8, une route de 1 à 3 avec un poids de 8 aussi, et une route de 2 à 5 avec un poids de 3.
En utilisant les données d'entrée, recherchez entre quelles planètes le Bureau va décider de placer les deux déviations pour minimiser le poids du réseau routier. Votre équipe pourra alors tenter de prévenir les planètes menacées par la déviation.
Si par exemple, vous pensez que les deux déviations seront placées entre 1 et 3 d'une part et entre 12 et 20 d'autre part, donnez la réponse sous cette forme :
(1, 3), (12, 20)
Peu importe l'ordre dans lequel vous donnez chacune des deux déviations, ni l'ordre dans lequel vous donnez les points de chaque déviation.
