Tour de parc – Épreuve régionale 2017

Énoncé¶

Ce matin, Joseph Marchand s'est lancé dans une visite du parc près de la grande fontaine de la région située à quelques lieues de sa maison de vacances. Ce parc a une particularité : il n'est possible de s'y promener que par un chemin faisant un tour circulaire extérieur au parc. Et de ce chemin il est possible d'appécier l'ensemble du parc.

Le chemin lui même est accessible par quelques sentiers forestiers, chacun débouchant à un endroit donné du chemin, qu'on appelle alors intersection. Le chemin possède $N$ intersections, et Joseph connaît les distances entre chaque paire d'intersections adjacentes :

• $d_1$ est la distance entre la première et la seconde intersection;
• $d_2$ est la distance entre la deuxième et la troisième intersection; $\dots$
• $d_{n-1}$ est la distance entre la $(n-1)$-ème et la $n$-ème intersection;
• $d_n$ est la distance entre la $n$-ème et la première intersection.

Après quelques heures de visite, Joseph commence à ressentir la fatigue et souhaite rentrer chez lui, il se trouve actuellement à l'intersection $s$ et souhaite retourner à l'intersection $t$ depuis laquelle il est arrivé.

Quelle est la distance la plus courte pour que Joseph retourne à l'intersection $t$ ?

Entrée¶

L'entrée comprendra plusieurs lignes :

• La première ligne contiendra trois entiers $N$, $s$ et $t$ le nombre d'intersections, l'intersection où se trouve actuellement Joseph, et l'intersection où il souhaite retourner.
• $N$ lignes suivront, la i-ème d'entre elles contiendra la distance $d_i$.

Sortie¶

Vous afficherez un entier : la distance minimale que Joseph doit parcourir pur aller de l'intersection $s$ vers l'intersection $t$.

Contraintes¶

• $1 \le N \le 1\ 000$
• $1 \le s, t \le N$
• $1 \le d_i \le 1\ 000$