Viikko 11: TMC-tehtävät

Tehtävien deadline: su-ma yö 25.4. 1:59.

Viikon aiheena on lyhimmät polut painotetuissa verkoissa. Tarvittavia algoritmeja ovat mm. Dijkstran algoritmi ja Floyd-Warshall. Lyhyt opas Dijkstran toteuttamisesta käytännössä. Ohessa on vielä video, jossa selitetään Dijkstran algoritmi leveyshaun laajennoksena.

Tehtävä 1

Sinulle on annettu tieverkosto, ja tehtäväsi on etsiä lyhimmän reitin pituus kaikkien kaupunkiparien välillä. Jokaista kahta kaupunkia yhdistää yksi suora tie.

Toteutus

Toteuta seuraava metodi:

long[][] lyhinReitti(int n, long[][] et)

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

Tieverkosto on annettu vierusmatriisiesityksessä. Luku et[i][j] kertoo kaupunkeja i ja j yhdistävän tien pituuden. Verkosto on suuntaamaton painotettu verkko, eli et[i][j]=et[j][i]. Kaikilla i=1..n pätee et[i][i]=0.

Algoritmisi palauttaman taulukon kaksiulotteisen taulukon lyhin, tulee olla yhtä suuri kuin syötteenä annettu taulukko et. Luvun lyhin[i][j], missä i,j ovat välillä 1..n, pitää kertoa lyhimmän polun i -> j pituus.

Esimerkki

Jos syötteenä annettu matriisi on

long[][] et1={{0,0,0,0,0},
              {0,0,9,1,2},
              {0,9,0,3,1},
              {0,1,3,0,7},
              {0,2,1,7,0}};

long[][] v1= {{0,0,0,0,0},
              {0,0,3,1,2},
              {0,3,0,3,1},
              {0,1,3,0,3},
              {0,2,1,3,0}};

Tehtävä 2

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, long[] matka)

Parametri n on kaupunkien määrä. Se on kokonaisluku välillä 1..10⁵. 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ä 3

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ä 4

Kyberhyökkäys on kaatanut suomen tietoverkot, mikä estää pääsysi iltasanomien nettisivuille. Verkkoa korjataan yhteys kerrallaan, kunnes kaikki yhteydet on saatu korjattua. Tehtävänäsi on selvittää, mihin aikaan saat taas yhteyden suosikkiuutissivustoosi.

Toteutus

Toteuta seuraava metodi:

long yhteysaika(int n, int[] mista, int[] minne, long[] milloin)

Parametri n on verkon koneiden määrä. Se on kokonaisluku välillä 1..10⁵. Koneet on numeroitu tuttuun tapaan kokonaisluvuin 1..n. Sinun koneesi on kone numero 1 ja iltasanomien nettisivu löytyy koneelta numero n.

Taulukot mista, minne ja milloin kuvaavat tietoverkon korjaustöiden etenemistä. Tiedot ovat muotoa "ajanhetkellä milloin[i] muodostuu koneiden mista[i] ja minne[i] välille yhteys". Kaikki yhteydet ovat kaksisuuntaisia! Näiden taulukoiden pituus on korkeintaan 10⁵. Taulukon milloin sisältämät luvut ovat välillä 1..10¹⁸.

Metodisi tulee palauttaa pienin ajanhetki, jolloin tietoverkossa on tarpeeksi korjattuja yhteyksiä, jotta yhteyden muodostaminen koneesta 1 koneeseen n on mahdollista. Voit olettaa, että tämä on aina mahdollista, kunhan kaikki yhteydet on korjattu.

Esimerkit

Tehtävä 5

Haluat matkustaa mahdollisimman halvalla Suomesta Australiaan, joten olet varautunut lentämään useaa lyhyempää lentoa käyttäen. Käytössäsi on lisäksi yksi alennuskuponki, jolla voit puolittaa yhden lennon hinnan (parittomalla hinnalla pyöristetään vielä alaspäin). Tehtävänäsi on selvittää, mikä on halvin hinta, jolla pääset Suomesta Australiaan.

Toteutus

Toteuta seuraava metodi:

long halvinReitti(int n, int[] mista, int[] minne, long[] hinta)

Parametrit kuvaavat lentokentät ja niiden väliset lennot samalla tavalla kuin aiemmissa tehtävissä. Kaikki lennot ovat yksisuuntaisia. Lentokenttien määrä on välillä 1..10⁵ ja samoin lentojen määrä on välillä 1..10⁵. Jokaisen lennon hinta on välllä 1..10⁹.

Aloitat matkasi lentokentältä numero 1 ja kohteenasi on lentokenttä numero n. Metodisi on palautettava halvimman mahdollisen lentoyhdistelmän hinta.

Tehtävän aikaraja on poikkeuksellisesti 2s.

Esimerkit