Sist endret: 23.09.2016  
 

Praksisoppgave - MsAlgoFan på ferie

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 13.11.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
alletilalle.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
alletilalle.py Funksjonen korteste_rute(rekkefolge, nabomatrise, byer) og innlesing av nabomatrise fra input.
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 5
umulig

Oppgave

For å hjelpe den uskyldige studinen å finne den billigste måten å gjennomføre turen sin på, må du finne den korteste veien innom alle byene i den oppgitte rekkefølgen. Det finnes flere måter å implementere dette på, men å bruke en eller annen form for korteste-vei algoritme er nok et godt utgangspunkt.

Input består av følgende linjer:

  1. Antall tester som følger (input-eksempelet har f.eks. to tester).
  2. Antall byer(n) som skal besøkes.
  3. Rekkefølgen byene skal besøkes i.
  4. De neste n linjene er en nabomatrise, bestående av n integere per linje, som beskriver hvor mye det koster å reise fra en by til en annen. (Linje 3, tall nummer 4 beskriver for eksempel hvor mye det koster å reise fra by nummer tre til by nummer 4).

Merk følgende:

  • Det koster alltid 0 kroner å reise fra en by til seg selv.
  • Hvis det ikke går ann å komme seg direkte fra by i til by j vil tall j på linje i være -1. Det vil si at -1 betyr ingen kant, og 0 betyr med andre ord at det er gratis å reise mellom de to byene.
  • Hun skal alltid returnere til den byen hun kom fra!
  • Byer kan besøkes flere ganger, men vil bare telle når besøkt i riktig rekkefølge. For rekkefølgen 1 0 2 vil for eksempel 1 2 0 2 1 være lov, mens 1 2 0 1 vil ikke være lov.

For hver test så skal output bestå av en linje bestående av et tall; den laveste mulige kostnaden for å fullføre turen. Om det er umulig å besøke alle byene, så skal output være umulig.

Rammeverk

from sys import stdin, maxsize

def shortest_path(order_list, adjacency_matrix, cities):
    # SKRIV DIN KODE HER

testcases = int(stdin.readline())
for test in range(testcases):
    cities = int(stdin.readline())
    order_list = [int(city) for city in stdin.readline().split()]
    adjacency_matrix = []
    for city in range(cities):
    # SKRIV DIN KODE HER
    print(shortest_path(order_list, adjacency_matrix, cities))

Variabelbeskrivelse

Rammeverket lager folgende variabler for deg: 'rekkefolge' er en liste med tall som sier hvilken rekkefolge byene skal besokes i. Tallene i listen er altsaa indeksene til byene. [0, 2, 1] betyr altsaa at by 0 skal besokes forst, deretter by 2, faar by 1 til slutt. 'nabomatrise' er en nabomatrise for byene, som sier noe om hvor dyrt det er aa reise fra en by til en annen. 0 3 -1 1 0 1 1 3 0 Nabomatrisen over, betyr at det er gratis aa reise fra by 0 til by 0, fra by 1 til by 1, og fra by 2 til by 2. Det betyr ogsaa at kostnaden for aa reise fra by 0 til by 1 er 3, og at det er umulig aa reise direkte fra by 0 til 2, osv. 'byer' er et tall som sier hvor mange byer det er, altsaa hoyden og bredden til nabomatrisen. Dersom du fortsatt er usikker pà variablene kan det vaere smart aa printe de og se hva de faktisk inneholder.

Input-eksempel

2
3
0 2 1
0 1 2
1 0 1
1 3 0
2
0 1
0 -1
1 0

Tilhørende output

5
umulig

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit