Hide

Problem C
Esports on my Mind

Languages en is

Nú er loksins úrslitaleikurinn í Striker-Count að byrja. Allir meðlimir KFFÍ eru mættir og flatbakan er komin í hús. Atli ákvað að koma að horfa á leikinn þrátt fyrir að hafa ekki mikinn áhuga á Striker-Count. Atli fær því Berg til að útskýra hvernig leikurinn virkar.

Í Striker-Count keppa tvö fimm manna lið. Annað liðið er kallað bláa liðið og hitt liðið er kallað gula liðið. Í hálfleik skipta svo liðin um lit. Liðið sem vinnur leikinn fær eitt stig, og það lið sem fyrr fær tvö stig vinnur mótið. Leikirnir eru spilaðir á mismunandi borðum. Á hverju borði eru tvær sprengistæður sem bláa liðið á að verja frá gula liðinu. Gula liðið vill koma fyrir sprengju á stæðunum. Sprengjan tekur 40 sekúndur að springa og á meðan þarf gula liðið að verja sprengjuna svo bláa liðið aftengi hana ekki. Ef sprengjan springur, þá vinnur alltaf gula liðið umferðina. Annars, ef allir í öðru liðinu deyja tapar það lið umferðinni. Í síðasta lagi tapar gula liðið ef það nær ekki að koma fyrir sprengjunni eða drepa bláa liðið á tveimur mínútum. Fyrra liðið til að vinna 16 umferðir vinnur leikinn og hálfleikur er eftir 15 umferðir. Ef lokastaðan er 15:15 þarf að fara í bráðabana. Atli tekur fljótt eftir að í byrjun á hverri umferð hlaupa leikmenn af stað og koma sér fyrir á sömu stöðunum. Bergur útskýrir fyrir honum að leikmenn þurfa að flýta sér á suma staðina á borðinu í upphafi umferðar því það tekur liðin, um það bil, jafn langan tíma að komast þangað. Bergur kallar þessa staði vígvelli. Atli tekur þó eftir það tekur ekki alltaf sama tíma að komast á staðina. Bergur segir honum að stundum byrja leikmennirnir umferðina lengra frá stöðunum sem þeir vilja komast á, sumir leikmenn eru fljótari á milli staða en aðrir og leikmenn ferðast mishratt eftir því á hvaða vopnum þeir halda. Atla finnst því réttara að skoða mögulega vígvelli, staðir sem gætu orðið vígvellir. Hverju borði má lýsa sem stefndu, vigtuðu neti. Ef það er leggur frá hnút u til v með vigt w er hægt að fara frá hnút u til v á að meðaltali w tíma. Sérhver leggur e hefur einnig skekkju σe. Ef vigt e er w tekur minnst wσe tíma að ferðast eftir leggnum og mest w+σe. Atli vill skilgreina hnút sem mögulegan vígvöll ef til er σedeσe fyrir hvern legg e þannig að ef vigt allra leggja e, gefin með we, er skipt út fyrir we+de þá verður sá hnútur vígvöllur. Hnútur er vígvöllur ef bæði liðin eru jafn lengi að komast þangað ef þau fara bæði stystu mögulegu leið. Hvaða hnútar eru mögulegir vígvellir í upphafi umferðar?

/problems/hi.esportsonmymind/file/statement/is/img-0001.jpg
Mynd af netinu í sýniinntaki 3

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur n og m, með 1n,m105. Hér táknar n fjölda hnúta og m fjölda leggja. Næsta lína inntaksins inniheldur tvær heiltölur b og g, með 1b,gn. Talan b gefur upphafsstaðsetningu bláa liðsins og g gefur upphafsstaðsetningu gula liðsins. Gefið er að bg. Næstu m línur innihalda fjórar heiltölur u,v,w,σ, með 1u,vn, 1σw109. Þær tákna legg frá hnút u til v með vigt w og skekkju σ. Gefið er að netið inniheldur engar snörur og sérhvert (u,v) par í inntakinu kemur mest fyrir einu sinni.

Úttak

Úttakið skal innihalda þá hnúta sem eru mögulegir vígvellir, í vaxandi röð, á einni línu. Ef það er enginn mögulegur vígvöllur skal prenta ‘Thessi leikur verdur sennilega leidinlegur’.

Sample Input 1 Sample Output 1
5 6
1 5
1 2 5 2
1 3 1 1
1 4 2 1
3 4 1 1
5 2 2 1
5 4 5 1
2
Sample Input 2 Sample Output 2
4 4
1 4
1 2 10 1
1 3 5 1
4 2 5 1
4 3 10 1
Thessi leikur verdur sennilega leidinlegur
Sample Input 3 Sample Output 3
13 38
2 10
1 2 2 1
1 11 7 2
1 5 4 1
2 1 2 1
2 3 3 1
3 2 3 1
3 7 2 2
3 4 6 1
4 3 6 1
4 8 7 2
5 1 4 1
5 2 1 1
5 6 4 2
6 5 4 2
6 7 1 1
6 9 8 3
6 12 10 4
7 3 2 2
7 8 8 2
7 9 10 3
8 4 7 2
8 7 8 2
8 10 13 2
9 6 8 3
9 7 10 3
9 10 3 1
9 12 4 2
10 8 16 5
10 9 3 1
10 12 4 2
11 1 7 2
11 12 4 1
11 13 1 1
12 6 10 4
12 9 4 2
12 10 4 2
12 11 4 1
13 11 1 1
6 7 8 11 13
Hide