Az S. 103. feladat (2015. december)

S. 103. Egy országban \(\displaystyle N\) város található. Megbíztak minket, hogy tervezzünk utakat a városok közt úgy, hogy bármelyik városból bármelyikbe egyféleképp lehessen eljutni. Mivel egy út megépítésének költsége egyenesen arányos a hosszával, így szeretnénk minimalizálni a megépülő utak összes hosszát. Az országban nagy hegyek is vannak, ezért nem építhetünk utat bármely két város között, hanem csak a bemenő adatokban megadott \(\displaystyle M\) db utat lehet megépíteni. Az útépítést vállaló cég technikai okok miatt nem tud egy adott úthosszból háromnál többet megépíteni (max 3 egyformát ajánl), ezért az úthálózatot úgy kell kialakítani, hogy bármely hosszúságú útból legföljebb három szerepeljen benne. Kérdés, hogy hányféleképp tudjuk megépíteni a lehető legkisebb összhosszúságú úthálózatot.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et (\(\displaystyle 1\le N \le 50\;000\), \(\displaystyle 1\le M\le 200\;000\)), majd a következő \(\displaystyle M\) sorból az \(\displaystyle a_i\), \(\displaystyle b_i\), \(\displaystyle c_i\) szóközzel elválasztott egészeket, melyek jelentése: az \(\displaystyle a_i\) városból a \(\displaystyle b_i\) városba építhetünk \(\displaystyle c_i\) (\(\displaystyle 1\le c_i\le 1\;000\;000\)) hosszú kétirányú utat. A program írja a standard output első és egyetlen sorába a legrövidebb összhosszúságot, amelyből megépíthető a hálózat, illetve a lehetőségek számának \(\displaystyle 1\;000\;000\;007\)-tel vett osztási maradékát.

Magyarázat: Ha az 1 hosszúságú éleket, és bármelyik 2 hosszúságú élet választjuk, akkor kapjuk a legrövidebbet.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s103.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2016. január 11-én LEJÁRT.

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Csenger Géza, Erdős Márton, Gáspár Attila, Noszály Áron.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2015. decemberi informatika feladatai