OpenKattis
POwarmup23 svår: Grafer

Start

2022-11-10 16:00 CET

POwarmup23 svår: Grafer

End

2022-11-17 16:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -503 days 17:42:24

Time elapsed

168:00:00

Time remaining

0:00:00

Problem F
Efterlyst

Poliskonstapel Acsel behöver din hjälp med ett brådskande ärende, nämligen att fånga den farliga brottsligen Waxel. Waxel gömmer sig någonstans i en stad som består av $N$ olika platser, numrerade mellan $1$ och $N$, med $M$ dubbelriktade vägar som var och en ansluter två olika platser. Han befann sig länge på en viss plats $X$ (det är okänt vilken), men sedan så flyttade han sig till en annan plats $Y$ (som vi inte heller känner till) genom att färdas längs en sekvens av vägar.

Polisen har samlat in $K$ stycken vittnesmål från personer som såg Waxel. Därför vet de att Waxel besökte platserna $a_1, a_2, \dots , a_ K$ på vägen från $X$ till $Y$ (det är även möjligt att $a_ i = X$ eller $a_ i = Y$ för något $i$). Däremot vet de inte i vilken ordning platserna besöktes. Waxel kan dessutom ha besökt fler än dessa $K$ platser på vägen från $X$ till $Y$.

Din uppgift är nu att hjälpa polisen att hitta de platser som möjligtvis kan vara $Y$, under förutsättning att Waxel tog en kortaste sekvens av vägar1 från $X$ till $Y$. Det är möjligt att det inte finns några sådana platser alls, om vittnesmålen inte stämmer överens med någon kortaste väg.

Indata

Den första raden innehåller tre heltal:

  • antalet platser i staden, $N$ ($2 \leq N \leq 2\cdot 10^5$),

  • antalet vägar i staden, $M$ ($1 \leq M \leq 2 \cdot 10^5$), och

  • antalet vittnesmål, $K$ ($1 \leq K \leq N$).

Den andra raden innehåller de $K$ olika heltalen $a_1, \dots , a_ K$ ($1 \leq a_ i \leq N$), de platser som Waxel besökte.

De $M$ följande raderna beskriver de olika vägarna i staden. Den $i$:te raden innehåller de tre heltalen $u_ i$, $v_ i$ ($1 \leq u_ i \not= v_ i \le N$) och $w_ i$ ($1 \leq w_ i \leq 10^9$), vilket innebär att den $i$:te vägen förbinder platserna $u_ i$ och $v_ i$ och har längd $w_ i$ meter. Det är garanterat att det går att ta sig mellan vilka två platser som helst genom att färdas längs en sekvens av vägar och att det mellan varje par av platser finns högst en väg som förbinder platserna.

Utdata

På den första raden ska du skriva ut antalet noder som kan vara $Y$. Notera att detta tal kan vara $0$.

På den andra raden ska du skriva ut samtliga noder som kan vara $Y$. Dessa ska skrivas ut separerade av blanksteg i ökande ordning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$5$

Det finns exakt $N - 1$ vägar, som förbinder platserna $1$ och $2$, $2$ och $3$ osv. upp till $N - 1$ och $N$

$2$

$16$

Det finns bara en sekvens av (icke-upprepande) vägar mellan varje par av platser, vilket har som konsekvens att $M = N - 1$

$3$

$15$

$N,M \leq 100$

$4$

$17$

$N,M \leq 1\, 000$

$5$

$15$

$N,M \leq 10^5$ och $K \leq 5$

$6$

$32$

Inga ytterligare begränsningar

Förklaring av exempelfall

I exempel $1$ är platserna $1,2,4,5$ möjliga mål för Waxel. För att komma till $2$ hade han kunnat ta vägen $5-6-1-2$.

I exempel $2$ finns det ingen kortaste väg som passerar de givna noderna. Svaret är alltså $0$.

I exempel $3$ finns det ganska många möjligheter. För att komma till $2$ hade Waxel t.ex. kunnat ta vägen $6-7-5-3-1-2$.

Sample Input 1 Sample Output 1
6 6 2
1 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
4
1 2 4 5
Sample Input 2 Sample Output 2
4 3 3
2 3 4
1 2 3
1 3 5
1 4 4
0

Sample Input 3 Sample Output 3
7 9 2
5 1
2 3 3
2 1 1
3 1 2
3 5 2
1 4 1
5 4 3
5 6 5
5 7 2
6 7 1
5
1 2 5 6 7
Sample Input 4 Sample Output 4
5 4 2
2 4
2 5 1
2 1 1
1 4 1
4 3 1
4
2 3 4 5

Footnotes

  1. Detta innebär att summan av längderna av de vägar som Waxel färdades längs är så liten som möjligt.