Problembeschreibung
Im Königreich JOI gibt es $N$ Städte, die durch $M$ in beide Richtungen befahrbare Straßen miteinander verbunden sind. In $K$ Städten gibt es Einkaufszentren, und die Bürger reisen über die Straßen in eine dieser Städte, um einzukaufen.
Je nach Lage eines Hauses muss man unter Umständen eine weite Strecke zurücklegen, um einkaufen zu gehen, was sehr unpraktisch ist. Um diese tatsächliche Situation zu erfassen, beschloss der König zu untersuchen, wie groß die kürzeste Entfernung zu einer Stadt mit einem Einkaufszentrum je nach Lage eines Hauses höchstens werden kann. Da ein Haus auch mitten auf einer Straße gebaut sein kann (siehe die Erklärung zu Beispiel $1$), ist diese Untersuchung sehr aufwendig. Deshalb hat der König dich, einen hervorragenden Programmierer, gebeten, ein Programm zu schreiben, das diese Untersuchung durchführt.
Schreibe ein Programm, das anhand der Informationen über die Straßen und die Städte mit Einkaufszentren die Entfernung von den Städten mit Einkaufszentren zum am weitesten entfernten Punkt auf einer Straße (einschließlich der Endpunkte) bestimmt. Die Entfernung, die für die Bewegung innerhalb einer Stadt benötigt wird, kann ignoriert werden.
Eingabe
Lies die folgende Eingabe von der Standardeingabe:
- Die $1$. Zeile enthält durch Leerzeichen getrennt die ganzen Zahlen $N, M, K$. $N$ steht für die Anzahl der Städte im Königreich JOI, $M$ für die Anzahl der Straßen im Königreich JOI und $K$ für die Anzahl der Städte mit einem Einkaufszentrum. Die Städte sind mit $1, 2, \dots, N$ nummeriert.
- Die folgenden $M$ Zeilen stellen die Informationen über die Straßen dar. Die $(i + 1)$. Zeile ($1 \le i \le M$) enthält durch Leerzeichen getrennt die ganzen Zahlen $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$). Dies bedeutet, dass die $i$-te Straße die Stadt $a_i$ und die Stadt $b_i$ verbindet und die Länge $l_i$ hat. Die beiden Enden einer Straße sind niemals dieselbe Stadt. Außerdem gibt es für beliebige $2$ Städte $p, q$ niemals $2$ oder mehr Straßen, die $p$ und $q$ direkt verbinden. Man kann von jeder Stadt zu jeder anderen Stadt gelangen, indem man einigen Straßen folgt.
- Die folgenden $K$ Zeilen stellen die Informationen über die Einkaufszentren dar. Die $(i + M + 1)$. Zeile ($1 \le i \le K$) enthält $1$ ganze Zahl $s_i$ ($1 \le s_i \le N$). Dies bedeutet, dass es in der Stadt $s_i$ ein Einkaufszentrum gibt. Unter $s_1, \dots, s_K$ kommt derselbe Wert niemals $2$-mal oder öfter vor.
Ausgabe
Gib auf der Standardausgabe $1$ ganze Zahl aus: das auf die nächste ganze Zahl kaufmännisch gerundete Maximum der kürzesten Entfernung zu einer Stadt mit einem Einkaufszentrum.
Beispiel
Beispiel 1
Eingabe
3 3 1 1 2 1 2 3 1 3 1 1 1
Ausgabe
2
Erklärung
Eingabebeispiel $1$ stellt die in der Abbildung unten gezeigten Städte dar. Die Längen aller Straßen betragen $1$. Ein Einkaufszentrum gibt es nur in Stadt $1$.
Der von einer Stadt mit Einkaufszentrum am weitesten entfernte Punkt liegt auf der Straße, die Stadt $2$ und Stadt $3$ verbindet, im Abstand von $0.5$ zu Stadt $2$, und seine Entfernung zur Stadt mit Einkaufszentrum beträgt $1.5$. Daher wird der gerundete Wert $2$ ausgegeben.
Beispiel 2
Eingabe
4 5 2 1 2 4 1 3 1 2 3 2 2 4 2 3 4 1 2 4
Ausgabe
3
Bedingungen
- $2 \le N \le 3000$: die Anzahl der Städte im Königreich JOI.
- $1 \le M \le 100000 = 10^5$: die Anzahl der Straßen im Königreich JOI.
- $1 \le K \le N$: die Anzahl der Städte mit einem Einkaufszentrum.
- $1 \le l_i \le 1000$: die Länge der $i$-ten Straße.
Bewertung
- Für Testdaten im Wert von $40\%$ der Gesamtpunktzahl gilt $K = 1$.