Prologin
2024
Énoncé¶
Les administrateurs de l'empire ont trouvé comment financer le prochain projet de l'étoile noir : les radars de limite de vitesse lumière !
Seulement, mettre en place des routes interplanétaires coûte assez cher, le but est donc de minimiser la longueur de routes à mettre en place (tout en liant toutes les planètes de l'empire), et ensuite, sur l'ensemble de ces routes passer un nombre de contrats avec des prestataires maximisant le nombre de radars posé.
Vous disposez d'une liste des routes possibles, chacune de ces routes relie deux planètes et est d'une longueur donnée. Il vous revient de calculer la longueur minimale de route que vous devez mettre en place pour qu'aucune planète ne soit isolée.
Les contrats de pose de radars se présentent sous la forme de contrats pour couvrir une distance $d_j$ de route avec $r_j$ radars. La portion de route couverte n'a pas à être continue, mais deux opérateurs ne peuvent pas travailler sur une même portion de route et un même contrat ne peux pas être signé plusieurs fois.
Entrée¶
L'entrée contiendra :
- Sur la première ligne, un entier : $N$, le nombre de planètes à relier.
- Sur la ligne suivante, un entier : $M$, le nombre de routes possibles.
- Sur les lignes suivantes, une liste de $M$ éléments : routes, la liste des
routes possibles.
- Une ligne par élément de la liste : séparés par des espaces, un entier $a_i$ (la planète à une extrémité de la route), un entier $b_i$ (la planète à l'autre extrémité de la route) et un entier $l_i$ (la longueur de la route) pour $i$ allant de $1$ à $M$.
- Sur la ligne suivante, un entier : $C$, le nombre de contrats possibles.
- Sur les lignes suivantes, une liste de $C$ éléments : contrats, la liste
des contrats possibles.
- Une ligne par élément de la liste : séparés par des espaces, un entier $d_j$ (la distance de route nécessaire pour installer les radars), et un entier $r_j$ (le nombre de radars qui seront posés sur la distance donnée) pour $j$ allant de $1$ à $C$.
Sortie¶
Affichez la longueur minimale de route à construire pour relier toutes les planètes (l'entrée que l'on vous donne le permet toujours, aucune planète n'est isolée), puis sur la ligne suivant le nombre maximal de radars pouvant être installé sur ces routes.
Contraintes¶
- $1 \leq N \leq 2000$
- $1 \leq M \leq 20000$
- $1 \leq C \leq 100$
- $1 \leq a_i \leq N$
- $1 \leq b_i \leq N$
- $1 \leq l_i \leq 50$
- $1 \leq d_j \leq 2000$
- $1 \leq r_j \leq 2000$
