루미 알고리즘

#1468다이아Efterlyst

PO 2019 훈련 캠프코딩출제 Nils Gustafsson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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, …, 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ägar (Detta innebär att summan av längderna av de vägar som Waxel färdades längs är så liten som möjligt.) 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 ≤ N ≤ 2 · 10^5),
  • antalet vägar i staden, M (1 ≤ M ≤ 2 · 10^5), och
  • antalet vittnesmål, K (1 ≤ K ≤ N).

Den andra raden innehåller de K olika heltalen a_1, …, a_K (1 ≤ a_i ≤ 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 ≤ u_i ≠ v_i ≤ N) och w_i (1 ≤ w_i ≤ 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.

GruppPoängvärdeGränser
15Det finns exakt N - 1 vägar, som förbinder platserna 1 och 2, 2 och 3 osv. upp till N - 1 och N
216Det finns bara en sekvens av (icke-upprepande) vägar mellan varje par av platser, vilket har som konsekvens att M = N - 1
315N,M ≤ 100
417N,M ≤ 1000
515N,M ≤ 10^5 och K ≤ 5
632Inga 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.

예제

예제 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

예제 2

입력
4 3 3
2 3 4
1 2 3
1 3 5
1 4 4
출력
0

예제 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

예제 4

입력
5 4 2
2 4
2 5 1
2 1 1
1 4 1
4 3 1
출력
4
2 3 4 5

출처 표기

출처: Programmeringsolympiaden 2019년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.