Viikko 11: TMC-tehtävät

Tehtävien deadline: ma 30.11. klo 04:01

Viikon aiheena on lyhimmät reitit painotetussa verkossa, erityisesti Dijkstran ja Floyd-Warshallin algoritmeilla on käyttöä.

Tehtävä 1

Sinulle on annettu tieverkosto, ja tehtäväsi on etsiä lyhin reitti kahden kaupungin välillä.

Toteutus

Toteuta seuraava metodi:

long lyhinReitti(int n, int[] mista, int[] minne, int[] matka)

Parametri n on kaupunkien määrä. Se on kokonaisluku välillä 1..100. Kaupungit on numeroitu tuttuun tapaan kokonaisluvuin 1..n.

Taulukot mista, minne ja matka kuvaavat kaupunkien väliset tiet. Kaikki taulukot ovat samankokoisia, ja teiden määrä on välillä 1..10⁵. Taulukko mista kertoo, mistä kaupungista tie alkaa, taulukko minne kertoo, mihin kaupunkiin tie johtaa, ja taulukko matka kertoo tien pituuden. Kaikki tiet ovat kaksisuuntaisia, ja jokaisen tien pituus on kokonaisluku välillä 1..10⁹.

Metodin tulee palauttaa lyhimmän reitin pituus kaupungista 1 kaupunkiin n. Jos mitään reittiä ei ole olemassa, metodin tulee palauttaa -1.

Esimerkit

Tehtävä 2

Tämä on muuten sama kuin tehtävä 1, mutta kaupunkien määrä on välillä 1..10⁵. Saatat siis tarvita tehokkaamman algoritmin kuin tehtävässä 1.

Tehtävä 3

Sinulla on tiedot henkilöiden välisistä ystävyyssuhteista, ja tehtäväsi on etsiä kaksi henkilöä, jotka ovat mahdollisimman kaukana toisistaan ystäväverkostossa. Tämä liittyy väitteeseen, että kaikki maailman ihmiset tuntevat toisensa 7 henkilön kautta.

Oletetaan esimerkiksi, että henkilöt ovat A, B ja C. Tiedetään, että A tuntee B:n ja B tuntee C:n. Nyt kaukaisimmat henkilöt ovat A ja C, joiden etäisyys on 2.

Toteutus

Toteuta seuraava metodi:

int kaukaisimmat(int n, int[] mista, int[] minne)

Parametri n on henkilöiden määrä, kokonaisluku välillä 1..100. Taulukot mista ja minne kuvaavat ystävyyssuhteet, ja niissä on 1..10⁵ alkiota. Voit olettaa, että ystäväverkosto on yhtenäinen.

Metodin tulee palauttaa, mikä on suurin etäisyys kahden henkilön välillä ystäväverkostossa.

Esimerkit

Tehtävä 4

Sinulle on annettu tiedot juna- ja lentoyhteyksistä. Haluaisit matkustaa kaupungista toiseen niin, että matkan varrella on mahdollisimman vähän lentoja.

Oletetaan esimerkiksi, että kaupunkeja on 3. Kaupungista 1 pääsee junalla kaupunkiin 2. Lisäksi kaupungista 1 pääsee lentäen kaupunkiin 2 ja kaupungista 2 pääsee lentäen kaupunkiin 3. Kun haluat matkustaa kaupungista 1 kaupunkiin 3, pienin mahdollinen määrä lentoja on 1: kaupungista 2 on pakko lentää kaupunkiin 3, koska kaupunkiin 3 ei pääse muulla tavalla.

Toteutus

Toteuta seuraava metodi:

int lentomaara(int n, int[] juna1, int[] juna2, int[] lento1, int[] lento2)

Parametri n on kaupunkien määrä. Se on kokonaisluku välillä 1..10⁵. Kaupungit on numeroitu tuttuun tapaan kokonaisluvuin 1..n.

Taulukot juna1 ja juna2 kuvaavat junayhteydet. Taulukossa juna1 lukee, mistä kaupungista juna lähtee, ja taulukossa juna2 lukee, mihin kaupunkiin juna saapuu. Kaikki yhteydet ovat kaksisuuntaisia.

Taulukot lento1 ja lento2 kuvaavat lentoyhteydet. Taulukossa lento1 lukee, mistä kaupungista lento lähtee, ja taulukossa lento2 lukee, mihin kaupunkiin lento saapuu. Kaikki yhteydet ovat kaksisuuntaisia.

Sekä junia että lentoja on välillä 0..10⁵.

Metodin tulee palauttaa pienin lentojen määrä, jolla pääset kaupungista 1 kaupunkiin n. Jos mitään reittiä ei ole olemassa, metodin tulee palauttaa -1.

Esimerkit

Tehtävä 5

Uolevi aikoo mennä Maijan luokse lyhintä reittiä, mutta joskus reitti ei ole yksikäsitteinen. Tehtäväsi on laskea, montako erilaista lyhintä reittiä Uolevilla on valittavana.

Toteutus

Toteuta seuraava metodi:

long reittimaara(int n, int[] mista, int[] minne, int[] matka)

Parametrit kuvaavat kaupungit ja tiet samalla tavalla kuin aiemmissa tehtävissä. Kaupunkien määrä on välillä 1..10⁵ ja samoin teiden määrä on välillä 1..10⁵. Jokaisen tien pituus on välllä 1..10⁹.

Metodin tulee palauttaa, montako erilaista lyhintä reittiä on olemassa kaupungista 1 kaupunkiin n. Voit olettaa, että vastaus on enintään 10¹⁸.

Esimerkit