Tehtävien deadline: ma 20.4. klo 01:59
Viikon aiheena on lyhimmät reitit painotetussa verkossa, erityisesti Dijkstran ja Floyd-Warshallin algoritmeilla on käyttöä.
Sinulle on annettu tieverkosto, ja tehtäväsi on etsiä lyhin reitti kahden kaupungin välillä.
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..105.
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..109.
Metodin tulee palauttaa lyhimmän reitin pituus
kaupungista 1 kaupunkiin n
.
Jos mitään reittiä ei ole olemassa,
metodin tulee palauttaa -1.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | lyhinReitti(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {5, 3}) | 8 |
2 | lyhinReitti(3, new int[] {1, 1}, new int[] {2, 3}, new int[] {2, 3}) | 3 |
3 | lyhinReitti(3, new int[] {1, 2, 1}, new int[] {3, 3, 2}, new int[] {9, 1, 1}) | 2 |
4 | lyhinReitti(3, new int[] {1, 2, 1}, new int[] {3, 3, 2}, new int[] {1, 9, 9}) | 1 |
Tämä on muuten sama kuin tehtävä 1, mutta kaupunkien määrä on välillä 1..105. Saatat siis tarvita tehokkaamman algoritmin kuin tehtävässä 1.
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.
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..105 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.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | kaukaisimmat(3, new int[] {1, 2}, new int[] {2, 3}) | 2 |
2 | kaukaisimmat(3, new int[] {1, 1}, new int[] {2, 3}) | 2 |
3 | kaukaisimmat(3, new int[] {1, 2, 3}, new int[] {2, 3, 1}) | 1 |
4 | kaukaisimmat(4, new int[] {1, 2, 3}, new int[] {2, 3, 4}) | 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.
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..105.
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..105.
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.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | lentomaara(3, new int[] {1}, new int[] {2}, new int[] {1, 2}, new int[] {2, 3}) | 1 |
2 | lentomaara(3, new int[] {1}, new int[] {3}, new int[] {1, 2}, new int[] {2, 3}) | 0 |
3 | lentomaara(3, new int[] {}, new int[] {}, new int[] {1, 2}, new int[] {2, 3}) | 2 |
4 | lentomaara(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {1, 2}, new int[] {2, 3}) | 0 |
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.
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..105 ja samoin teiden määrä on välillä 1..105. Jokaisen tien pituus on välllä 1..109.
Metodin tulee palauttaa, montako erilaista lyhintä reittiä
on olemassa kaupungista 1 kaupunkiin n
.
Voit olettaa, että vastaus on enintään 1018.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | reittimaara(3, new int[] {1, 2}, new int[] {2, 3}, new int[] {5, 3}) | 1 |
2 | reittimaara(3, new int[] {1, 2, 1}, new int[] {2, 3, 3}, new int[] {2, 3, 5}) | 2 |
3 | reittimaara(5, new int[] {1, 1, 1, 2, 3, 4}, new int[] {2, 3, 4, 5, 5, 5}, new int[] {1, 1, 1, 1, 1, 1}) | 3 |
4 | reittimaara(5, new int[] {1, 1, 1, 2, 3, 4}, new int[] {2, 3, 4, 5, 5, 5}, new int[] {1, 2, 2, 1, 1, 1}) | 1 |