Énoncé du problème
Au Royaume JOI, il y a $N$ villes reliées entre elles par $M$ routes praticables dans les deux sens. $K$ villes possèdent un centre commercial, et les citoyens empruntent les routes pour se rendre dans l'une de ces villes afin d'y faire leurs courses.
Selon l'emplacement d'une maison, il peut être nécessaire de parcourir une longue distance pour aller faire ses courses, ce qui est très peu pratique. Pour appréhender cette situation réelle, le Roi a décidé d'étudier jusqu'à quelle valeur peut s'élever la plus courte distance vers une ville possédant un centre commercial, selon l'emplacement de la maison. Comme une maison peut aussi être construite au milieu d'une route (voir l'explication de l'Exemple $1$), cette étude est très difficile. C'est pourquoi le Roi vous a demandé, à vous qui êtes un excellent programmeur, d'écrire un programme réalisant cette étude.
Étant donné les informations sur les routes et sur les villes possédant un centre commercial, écrivez un programme permettant de déterminer la distance entre les villes possédant un centre commercial et le point situé sur une route (extrémités comprises) qui en est le plus éloigné. Vous pouvez négliger la distance nécessaire pour se déplacer à l'intérieur d'une ville.
Entrée
Lisez l'entrée suivante depuis l'entrée standard :
- La $1$-re ligne contient les entiers $N, M, K$ séparés par des espaces. $N$ représente le nombre de villes du Royaume JOI, $M$ le nombre de routes du Royaume JOI et $K$ le nombre de villes possédant un centre commercial. Les villes sont numérotées $1, 2, \dots, N$.
- Les $M$ lignes suivantes représentent les informations sur les routes. La $(i + 1)$-e ligne ($1 \le i \le M$) contient les entiers $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$) séparés par des espaces. Cela signifie que la $i$-e route relie la ville $a_i$ et la ville $b_i$, et que sa longueur est $l_i$. Les deux extrémités d'une route ne sont jamais la même ville. De plus, pour $2$ villes quelconques $p, q$, il n'existe jamais $2$ routes ou plus reliant $p$ et $q$. Il est possible d'aller de n'importe quelle ville à n'importe quelle autre en empruntant quelques routes.
- Les $K$ lignes suivantes représentent les informations sur les centres commerciaux. La $(i + M + 1)$-e ligne ($1 \le i \le K$) contient $1$ entier $s_i$ ($1 \le s_i \le N$). Cela signifie qu'il y a un centre commercial dans la ville $s_i$. Une même valeur n'apparaît jamais $2$ fois ou plus parmi $s_1, \dots, s_K$.
Sortie
Affichez sur la sortie standard $1$ entier : la valeur maximale de la plus courte distance jusqu'à une ville possédant un centre commercial, arrondie à l'entier le plus proche.
Exemple
Exemple 1
Entrée
3 3 1 1 2 1 2 3 1 3 1 1 1
Sortie
2
Explication
L'exemple d'entrée $1$ représente les villes illustrées sur la figure ci-dessous. Toutes les routes ont une longueur égale à $1$. Il n'y a de centre commercial que dans la ville $1$.
Le point le plus éloigné d'une ville possédant un centre commercial est le point situé sur la route reliant la ville $2$ et la ville $3$, à une distance de $0.5$ de la ville $2$, et sa distance à la ville possédant un centre commercial est de $1.5$. Par conséquent, on affiche $2$, qui est sa valeur arrondie à l'entier le plus proche.
Exemple 2
Entrée
4 5 2 1 2 4 1 3 1 2 3 2 2 4 2 3 4 1 2 4
Sortie
3
Contraintes
- $2 \le N \le 3000$ : le nombre de villes du Royaume JOI.
- $1 \le M \le 100000 = 10^5$ : le nombre de routes du Royaume JOI.
- $1 \le K \le N$ : le nombre de villes possédant un centre commercial.
- $1 \le l_i \le 1000$ : la longueur de la $i$-e route.
Barème
- Pour des jeux de tests valant $40\%$ du score total, $K = 1$ est vérifiée.