Una sola escala P66083
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.
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
- Author
- Jordi Cortadella i Jordi Petit
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++ Python