Egyetemünk hallgatóinak a regionális ACM versenyen résztvevő csapata a verseny befejezése után városnézésre akar menni. Nincs sok idejük, így megkeresik a legrövidebb útvonalat, amelyik a szállodától indul és ott végződik. A csapat beszerezte a város térképét, amely megadja az utcák hosszát. Bár minden utca kétirányú, a csapat nem akar egy úton két irányban is végigsétálni.Feladat:
Írj programot, amely megadja a legrövidebb utat!Bemenet:A bemenet néhány tesztesetet tartalmaz, mindegyik leír egy elképzelt várostérképet. Az útkereszteződéseket 1 és N közötti egészek azonosítják. Minden teszteset első sora három egészet, az N, K és M számokat tartalmazza (1<=K<=N<=1000), ahol N az útkereszteződések száma, K a kiindulási pont sorszáma, M (1<=M<=20000) a kétirányú utak száma. A következő M sor három-három egészet tartalmaz, az a, b, h számokat (1<=a, b<=N, 1<=h<=10000), ahol a és b útkereszteződések, h pedig a két sarok közötti távolság. Minden a, b párhoz legfeljebb egy kétirányú utca tartozik.Kimenet:A 0 0 0 számhármassal zárul az adatbevitel.
A kimeneti állomány a tesztesetek számának megfelelő számú sort tartalmaz. Ha nem tehetünk ilyen körutat, akkor a "No solution" szöveg kerüljön az állományba, ha van megoldás, akkor pedig az út során érintett sarkokat reprezentáló számokat! A kiindulási és érkezési pont azonos, azt csak egyszer kell kiírnod.Példa:
trip.in trip.out 6 1 8
1 2 1
2 4 3
1 3 1
3 4 2
4 6 1
4 5 1
5 6 1
1 5 1
4 1 1
1 2 1
0 0 01 3 4 5
No solution
Egy kommunikációs hálózat eszközökből és az őket összekötő kétirányú vezetékekből áll. Az eszközök egyikét a hálózat középpontjának jelöljük ki. A középpontnak bármely eszköztől indulva elérhetőnek kell lennie egy vagy több kommunikációs vonal felhasználásával. A megvalósított hálózat nem garantálja a középpont elérését.Feladat:
Írj programot, amely minimális számú új kommunikációs vonal létrehozásával elérhetővé teszi a középpont elérését bármely más eszközből. Emellett a program adja meg az új kapcsolatok végpontjait!Bemenet:A bemeneti állomány néhány tesztesetet tartalmaz, amelyek hálózatot írnak le. Minden teszteset első sora három egészet, az N K és M értékét tartalmazza. Az N (1<=N<=1000) a hálózati eszközök számát adja meg, a K (1<=K<=N) a kijelölt középpont sorszáma és az M (1<=M<=5000) a kommunikációs kapcsolatok számát adja meg. Az ezt követő M sor mindegyikében egy-egy a, b számpár áll, ahol (1<=a, b<=N) egy kommunikációs kapcsolat két végpontja.Kimenet:A 0 0 0 sor zárja a bemeneti állományt.
A kimenet tesztesetenként két sort tartalmaz. Az első sor egyetlen U egész számot tartalmaz, amely a szükséges kommunikációs vonalak számát adja meg. A következő sor U számpárt tartalmaz, amelyet az a, b egészek alkotnak, egy-egy kommunikációs csatorna végpontjait adják meg. Ha az U értéke 0, akkor a következő sornak üresnek kell lennie.Példa:
centre.in centre.out 3 1 3
1 3
3 2
2 1
8 1 10
1 2
2 3
3 1
4 5
5 7
7 6
6 5
4 8
4 1
4 7
0 0 00 2
7 1 8 1