Una sola escala P66083


Statement
 

pdf   zip

thehtml

Tenim el cost dels vols entre n parells de ciutats enmagatzemats en una matriu m tal que mi,j representa el cost de volar de la ciutat i a la ciutat j. Donades dues ciutats a i b i un valor limit c, volem saber totes les escales que es poden fer per viatjar de la ciutat a a la ciutat b amb un cost inferior o igual a c.

Entrada

L’entrada comença amb el nombre de ciutats, un natural n. A continuació ve la matriu n× n amb els costos dels vols, que també són naturals. El cost de viatjar d’una ciutat a ella mateixa és zero però els costos no tenen perquè ser simètrics. Finalment, ve una seqüència de tripletes de naturals a,b,c, indicant que es volen les escales per viatjar de la ciutat a a la ciutat b amb un cost inferior o igual a c. Es té que 0≤ a,b<n.

Sortida

Per a cada tripleta a,b,c, cal escriure la llista de ciutats que permeten fer l’escala (o res si no n’hi ha cap). Seguiu el format dels exemples i fixeu-vos que és lícit utilitzar la ciutat de sortida o d’arribada com a escala.

Public test cases
  • Input

    4
    
    0 3 4 2
    3 0 5 1
    4 5 0 6
    2 1 6 0
    
    0 3 10
    0 3 2
    0 2 3
    1 2 5
    1 1 0
    
    

    Output

    0 3 10: 0 1 2 3
    0 3 2: 0 3
    0 2 3: res
    1 2 5: 1 2
    1 1 0: 1
    
  • Input

    6
    
    0 4 5 6 1 2
    4 0 2 2 9 1
    5 1 0 3 2 1
    4 4 2 0 9 11
    9 2 3 7 0 1
    5 6 7 2 3 0
    
    1 2 6
    1 2 10
    

    Output

    1 2 6: 1 2 3
    1 2 10: 0 1 2 3 5
    
  • Information
    Author
    Jordi Cortadella i Jordi Petit
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python