Lopputyö kurssiin Tietorakenteet ja algoritmit

Tehtävänanto:
Erään maan teillä on paljon painorajoitettuja
siltoja. K. on kuorma-autoyrittäjä maan eräässä kaupungissa ja hän kuljettaa kuormia
kotikaupungistaan muualle maahan. K:n ainoa kuorma-auto painaa 8 tonnia ja sen kuorman
painolla ei ole ylärajaa. Ottaessaan työn vastaan K. haluaa tietää, kuinka painavan kuorman hän
voi viedä päämäärään kertakuljetuksella. Tätä varten reittivaihtoehdot muotoillaan
suuntaamattomana verkkona, jonka solmuja ovat kaupungit ja väleinä niiden väliset tiet. Kaikkien
kaupunkien välillä ei kulje suoraa yhteyttä. Väli painotetaan tiellä kuljetettavan maksimipainon
mukaan. Painot merkitään täysinä tonneina. Kaupungit numeroidaan kokonaisluvuilla alkaen
luvusta 1 siten, että 1 on aina kuorman lähtöpaikka.
Tässä työssä laaditaan autoilija K:lle apuohjelma, jolle syötetään tieverkko rajoituksineen
tekstitiedostona seuraavasti: Ensimmäisellä rivillä on välilyönnillä erotettuna kaupunkien
lukumäärä ja teiden lukumäärä. Sitten luetellaan kukin omalla rivillään tiet rajoituksineen
lukukolmikkoina: lähtökaupunki, maalikaupunki, painorajoitus. Viimeisellä rivillä on kaupunki,
johon reittiä haetaan. Esimerkiksi edellä olevan tieverkon esitys määränpäänään kaupunki 7 olisi
tiedostona

Mukana testidataa ja oikeat vastaukset