Newsgroup: it.comp.lang.c
Titolo: Problema

Vi chiedo come risolvereste questo problema, dato che la risoluzione
non mi è affatto ovvia :-((
Voglio calcolare la lunghezza di un fiume (o di parte di un fiume)
come somma di  piccoli percorsi, senza che il loro inserimento avvenga
in modo ordinato.
Esempio di input:
punto3 punto2 52
punto4 punto3 45
punto1 punto2 35
Dove il numero indica la distanza tra i due punti e puntoX è il nome
di un punto ("ponte", "roccia", ...)
Non insultatemi :-(

 cut

 punto1 punto2 35
se i dati che hai sono sempre nella forma
punto(N) punto(N+1) DISTANZA
oppure
punto(N) punto(N-1) DISTANZA
la soluzione piu' semplice da implementare credo sia tramite un array, di
X+1 elementi (X=numero totale dei tratti nei quali è diviso il fiume).
Una volta letto l'input, determini l'N maggiore tra i 2 punti che hai, mi
spiego meglio:
punto3 punto2 52   (in questo caso punto3 è il maggiore)
punto1 punto2 35   (questa volta è ovviamente maggiore punto2)
Nella posizione N dell'array metti la distanza (quindi la posizione N
rappresenta la distanza che c'è tra N e N-1).
Per calcolare la distanza tra 2 punti (X e Y) basta che fai la somma delle
posizioni da X+1 a Y dell'array.
Ciao
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/GEmqQb6qi6QXZLkRAqdqAKCWgpXVyToxSH8tJEKv+XvPJiI6BACfVLBo
H8nJ95cSdVWX/Q5v90G5/Js=
=7Loj
-----END PGP SIGNATURE-----

 Una volta letto l'input, determini l'N maggiore tra i 2 punti che hai, mi
-cut-
Non č cosě semplice :-(
Non posso fare cosě, perché i punti non sono identificati da numeri
progressivi in base alla loro posizione nel fiume, ma da stringhe (e non
stringhe del tipo "A", "B" etc).
Un elenco dei punti di un eventuale percorso lungo il fiume potrebbe essere:
roccia_nera
ponte
bandierina_blu
isolotto
Non posso confrontare ponte e bandierina_blu, ad esempio.

 Non posso confrontare ponte e bandierina_blu, ad esempio.
puoi fare una funzione che ritorni il numero progressivo del punto sul
percorso, identificato dalla stringa. Cosě puoi confrontare con qualcosa
tipo
if ((a=getindex("ponte")) > (b=getindex("bandierina_blu"))) {
        blah[a]=distanza;
} else {
        blah[b]=distanza;
}
Ciao
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/GJglQb6qi6QXZLkRAruFAJ9mVjWk+PGEMNEojRxZodNsm8oQCwCePDEe
oTuNi6yz/ZoqK+J7S2LVWUw=
=8Ehz
-----END PGP SIGNATURE-----

 }
Naturalmente cosě non ci potrebbero essere due "ponte" sullo stesso fiume...
Ciao
Antonio

 percorso, identificato dalla stringa.
[cut]
No, io al momento dell'inserimento dei dati da input non ho idea di come sia
il fiume, quindi non posso fare questa funzione. E' qui il difficile:
diciamo che è un programma che deve funzionare per tutti i fiumi, che io
ogni volta mi devo "costruire" in memoria per poi giocarci sopra :-)
Io so solo che da input ricevo tanti segmenti e questi formano una linea
spezzata.

 spezzata.
Se non hai un modo per stabilire l'ordinamento dei punti la vedo molto dura.
Per una sequenza di n tratti hai n! possibili fiumi e non hai modo di sapere
quale e' giusto.
Sicura che non esista un ordinamento?
Ma chi te li passa 'sti dati?
ciao,
Nids
ps: se nessuno sa l'ordine dei pezzi del fiume "montalo" cosi' come ti
arriva che sicuramente nessuno se ne accorge e fai anche alla svelta :)

 Sicura che non esista un ordinamento?
[cut]
Sì, anche se il testo dell'esercizio non ce l'ho più. Però ho trovato un
esercizio simile (almeno, a me sembrava simile) mi pare sul sito del
politecnico di Milano, o dell'università di Milano... boh qualcosa del
genere, non riesco più a pescarlo. Un altro esercizio simile l'ho trovato
spulciando il sito del politecnico di Torino, è qui:
http://webservices.polito.it/matdid/3ing_eln_L2170_TO_0/mat_comune/testiEsam
e/tpl/TLPT030704.doc
Il problema mi sembra fondamentalmente il medesimo, poi vabbè qui chiede più
cose, ma calcolare il ritardo tra due città è come calcolare la distanza tra
due punti del mio fiume!
Forse sto correndo troppo, sti esercizi qua son ancora troppo tosti per me,
ma ormai voglio sapere!
A me era venuto in mente di memorizzare ogni punto (o città) in un record al
cui interno piazzo anche la lista dei punti (al massimo due) che sono
comparsi in una stessa linea (del file di input) assieme a quel dato punto:
insomma, il punto precedente e quello successivo (se esistono) e le loro
distanze. Nel mio vettore di struct, i record (punti) rimangono
disordinati. Leggo a partire dal punto di partenza chiestomi dall'utente
(andandomelo a cercare nel vettore), poi ricorsivamente, inserisco i punti
in cui "passo" in un altro vettore. Controllo ogni volta se sono già
passato da quel punto o se ho raggiunto il punto finale, casi in cui dovrei
abbandonare il percorso considerato. Avendo di volta in volta sommato le
distanze
parziali, dovrei essere a posto.
Che ne dite?
Cmq grazie per l'attenzione, è bello vedere gente che si appassiona ai
problemi ed è pronta a discuterne!
;-)

 arriva che sicuramente nessuno se ne accorge e fai anche alla svelta :)
Devi avere per forza un modo per posizionare i vari punti sul fiume o almeno
posizionarli tra di loro. 
Partiamo da un esempio semplice (creato sul momento).
inizio                                                                  fine
|                                                                          |
+----+------------------+--------------+------------------+----------------+
     |                  |              |                  |
     "roccia"           "ponte"        "rapida"           "conca"
I casi sono 2:
1) hai tutte le sequenze in ordine e con questi punti puio coprire tutto il 
   fiume o almeno una parte continua di fiume (e' fondamentale che non ci 
   siano buchi):
       inizio -> roccia:  5
       roccia -> ponte:  19
       ponte  -> rapita: 15
       rapida -> conca:  19
       conca  -> fine:   17
2) Non ti sono date in ordine, ma sai la successione dei vari riferimenti: 
       riferimenti: roccia, ponte, rapida, conca
Altrimenti il problema non si risolve perche' hai informazioni incomplete
(non penso che il fiume si possa comporre a gradimento come un puzzle :P).
Se si verifica il primo caso ti basta una lista di riferimenti che
costruisci man mano:
+--------+          +--------+           +-------+            +------+
| inizio | --(5)--> | roccia | --(19)--> | ponte | -- ... --> | fine |
+--------+          +--------+           +-------+            +------+
Poi nell'implementazione la distanza diventa un attributo del nodo, ma
concettualmente e' un attributo dell'arco che unisce 2 nodi.
Nel secondo caso potresti direttamente avere un array:
struct array {
  char *nome_riferimento;
  int distanza_dal_successivo;
}
struct array fiume [NUMERO_ENTRY];
Man mano che leggi i dati completi una singola entry del tuo array (a sto
punto non ti importa in che ordine arrivano).
Se vuoi velocizzare la ricerca potresti usare un albero binario o una
tabella di hash come indice per il tuo array.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 (non penso che il fiume si possa comporre a gradimento come un puzzle :P).
No. C'e' anche il caso in cui le sequenze non siano in ordine, e tu non sai
la successione dei vari riferimenti.
In questo caso pero' e' fondamentale che non ci siano buchi e che non ci
siano segmenti di lunghezza maggiore di 1, ovvero ad esempio "roccia -
conca" non va bene!
Tra le altre cose i segmenti non devono per forza essere in ordine
crescente: inizio - roccia, ma anche roccia - inizio va bene!
Questa e' una maggiore complicazione ovviamente di cui bisogna tenere conto,
ma voglio considerarla per mostrare che e' ugualmente possibile. (senza
questa complicanza e' davvero banale altrimenti ;-)
Questo ovviamente solo al fine di trovare la distanza tra due segmenti o di
tutto il fiume, guarda....
Ecco la tua sequenza in ordine sparso e con anche l'ordine all'interno della
coppia in ordine sparso:
ponte  rapida 15
roccia inizio 5
ponte roccia 19
conca fine 17
rapida conca 19
Ok, costruiamo il fiume:
Leggiamo la prima riga e mettiamo da parte:
[ponte - rapida, 15]
leggiamo la seconda e mettiamola da parte:
[ponte - rapida, 15]
[roccia - inizio, 5]
* leggiamo la terza e attacchiamola alla prima (visto che in entrambe appare
ponte!):
[roccia - ponte, 19] - [ponte - rapida, 15]
[roccia - inizio, 5]
ora pero' possiamo fondere le due righe:
[inizio - roccia, 5] - [roccia - ponte, 19] - [ponte - rapida, 15]
leggiamo la quarta:
[inizio - roccia, 5] - [roccia - ponte, 19] - [ponte - rapida, 15]
[conca - fine, 17]
leggiamo la quinta ed attacchiamola:
[inizio - roccia, 5] - [roccia - ponte, 19] - [ponte - rapida, 15]
[rapida - conca, 19] - [conca - fine, 17]
attacchiamo il tutto:
[inizio - roccia, 5] - [roccia - ponte, 19] - [ponte - rapida, 15] -
[rapida - conca, 19] - [conca - fine, 17]
Ok, come ti sarai accorto, al punto con l'* potevo anche fare in modo
diverso, quindi facciamolo per evitare problemi...
* leggiamo la terza e attacchiamola alla prima (visto che in entrambe appare
ponte!):
[rapida -  ponte, 15] - [ponte - roccia, 19]
[roccia - inizio, 5]
ok, questo deriva dal fatto che non potevamo sapere se era "giusta" la
sequenza ponte-rapida oppure ponte-roccia, una delle due non e' in ordine
ovviamente (visto che i segmenti sono lunghi solo 1a unita'!)
Andiamo quindi avanti:
ora pero' possiamo fondere le due righe:
[rapida -  ponte, 15] - [ponte - roccia, 19] - [roccia - inizio, 5]
leggiamo la quarta:
[rapida -  ponte, 15] - [ponte - roccia, 19] - [roccia - inizio, 5]
[conca - fine, 17]
Ok, nel pezzo seguente invertiamo ancora la sequenza!
leggiamo la quinta ed attacchiamola:
[rapida -  ponte, 15] - [ponte - roccia, 19] - [roccia - inizio, 5]
[rapida - conca, 19] - [conca - fine, 17]
attacchiamo il tutto:
ora vediamo che le due sequenze sono in ordine inverso!
Sembra un problema, ma non lo e'!
Possiamo decidere di attaccare la seconda sequenza alla prima, un pezzo alla
volta, oppure la prima alla seconda un pezzo alla volta.
Nel primo caso otterremo il fiume al contrario, ma ai fini di calcolare la
distanza non e' assolutamente un problema!!
Nel secondo caso otteniamo il fiume al "giusto".
Facciamolo al contrario:
[fine - conca, 17] - [conca - rapida, 19] - [rapida -  ponte, 15] - [ponte -
roccia, 19] - [roccia - inizio, 5]
Ok in entrambi i casi, sia con:
[inizio - roccia, 5] - [roccia - ponte, 19] - [ponte - rapida, 15] -
[rapida - conca, 19] - [conca - fine, 17]
che con:
[fine - conca, 17] - [conca - rapida, 19] - [rapida -  ponte, 15] - [ponte -
roccia, 19] - [roccia - inizio, 5]
Il fiume e' nel giusto ordine.
Se io ti chiedo la distanza tra conca e ponte, in entrambi i casi la
risposta sara': 19+15 (o 15+19, ma non cambia!)
Tommy

 crescente: inizio - roccia, ma anche roccia - inizio va bene!
Sì, come mostrava anche il mio esempio.
Ma perché non commentate la mia soluzione (quella del mio messaggio
precedente, con il vettore dei punti toccati)? Io credo che funzioni e sia
anche la più immediata... Ora cmq vado a scriverla in codice, vediamo cosa
esce.

 sia il fiume, quindi non posso fare questa funzione. E' qui il difficile:
ah adesso finalmente ho capito com'è il problema. Dunque, io prima di tutto
acquisirei tutti i dati di input in strutture tipo
struct segment {
char *p1;
char *p2;
int distanza;
struct segment *next;
}
Una volta finiti i dati di input si puo' tentare di ricostruire il percorso.
supponendo di avere dati tipo (ometto la distanza che al momento è inutile)
D E
B A
E F
C B
C D
partiamo da D E, *next punta ora a NULL. Cerchiamo in tutti gli altri
segmenti quello che contiene o D o E (li cerchiamo entrambi xkè *next è
NULL), troviamo E F. Facciamo puntare il segment che contiene D E a quello
contenente E F. Stavolta cerchiamo un segmento che contenga E o F. Troviamo
ancora e solo D E; cerchiamo quindi un segmento che contenga solo D (in
quanto *next non è piu' NULL ed E l'ho già trovato. D'ora in poi cerchero'
solo i segmenti contenenti il primo punto delle struct).
Troviamo C D, facciamolo puntare a D E. Ora cerchiamo un segmento contenente
C (sempre perchè il *next non è NULL nella strut C D). Troviamo C B, ma non
va bene xkè sia in C D che in C B, C è l'elemento iniziale, quindi
invertiamo l'ordine di C B in B C, facciamo quindi puntare B C a C D.
Cerchiamo ora un altro segmento contenente B e troviamo B A, invertiamo
pure questo e facciamo puntare A B  ad B C.
Una volta ricostruito il percorso possiamo calcolare anche le distanze senza
grandi sforzi.
Ciao.
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/GTc4Qb6qi6QXZLkRAjSPAKCeu6Mh0k9XUVDtXQ0wYYjPrymcCQCgk84l
gPKWQmK57iLIWby8SBUdrsA=
=v7hl
-----END PGP SIGNATURE-----

 esce.
Perche' non ho capito molto di quello che hai detto!
Questa e' la mia soluzione. Ce ne sono di piu' eleganti e performanti, ma
questa e' la piu' semplice.
Prendi i segmenti (es. roccia conca 13) e li metti tutti i una lista:
ponte  rapida 15
roccia inizio 5
ponte roccia 19
conca fine 17
rapida conca 19
Bene ora hai una lista con i seguenti elementi, la lista li prende
semplicemente da un file o da tastiera. Ogni elemento della lista, come
mostrato sara' una struttura contenente 2 stringhe ed un intero.
Ora crei un'altra lista, quella che conterra' i segmenti ordinati e metti il
primo elemento dentro questa lista e lo cancelli dalla lista non ordinata:
Lista non ordinata:
--------------------
roccia inizio 5
ponte roccia 19
conca fine 17
rapida conca 19
Lista ordinata:
---------------------
ponte  rapida 15
Ora scorri la lista non ordinata fino a che non trovi un segmento che
contiene o "ponte" o "rapida". Saltiamo quindi roccia-inizio e troviamo
ponte-roccia. A questo punto ci sono da considerare 4 possibilita'....
Chiamiamo l'elemento della lista ordinata LO e LNO quello della lista non
ordinata. Chiamiamo inoltre s1 ed s2 le relative stringhe:
if (LO.s1==LNO.s1){
     // inserisci LNO invertendo l'ordine delle 2 stringhe prima di LO
}else if (LO.s1 == LNO.s2){
     // inserisci LNO prima di LO
}else if (LO.s2 ==  LNO.s1){
     // inserisci LNO dopo di LO
}else if (LO.s2 == LNO.s2){
     // inserisci LNO dopo di LO invertendo l'ordine delle due stringhe di
LNO
}
Bene, in questo caso LNO e' ponte-roccia e LO e' ponte-rapida. Ecco che si
verifca quindi il caso 1 e quindi invertiamo ponte-roccia in roccia-ponte e
lo inseriamo prima di LO e poi cancelliamo LNO:
Lista non ordinata:
--------------------
roccia inizio 5
conca fine 17
rapida conca 19
Lista ordinata:
---------------------
roccia ponte 19
ponte  rapida 15
Scorriamo ancora la lista, siamo arrivati a conca-fine, e cerchiamo un LNO
che abbia una delle parole di un qualsiasi LO. Abbiato trovato rapida-conca.
Questo e' un caso 3, quindi inseriamo LNO dopo l'LO trovato:
Lista non ordinata:
--------------------
roccia inizio 5
conca fine 17
Lista ordinata:
---------------------
roccia ponte 19
ponte  rapida 15
rapida conca 19
Ok, ora abbiamo finito di scorrere la lista non ordinata. Bene ripetiamo da
capo il processo fino a che la lista non ordinata non e' vuota! Ripartiamo
quindi da capo:
Riscorrendo la lista non ordinata troviamo LNO roccia-inizio e LO
roccia-ponte:
Lista non ordinata:
--------------------
conca fine 17
Lista ordinata:
---------------------
inizio roccia 5
roccia ponte 19
ponte  rapida 15
rapida conca 19
ora tocca a conca fine:
Lista non ordinata:
--------------------
Lista ordinata:
---------------------
inizio roccia 5
roccia ponte 19
ponte  rapida 15
rapida conca 19
conca fine 17
Ok, ora la lista non ordinata e' finita e la lista ordinata e' completa.
Come ho detto, sarebbe possibile ottenere la lista ordinata inversa, da fine
a inizio (invece che da inizio a fine). Questo e' inevitabile se le coppie
non sono in ordine; ma questo non e' un problema ai fini del calcolo delle
distanze!
Devo ammettere che l'algoritmo descritto non e' il modo piu' "performante"
per raggiungere il risultato voluto, ma e' certamente il piu' semplice da
implementare. Cicli e liste! Ecco tutto quello che serve!
Ora io ho implementato il seguente algoritmo. L'ho fatto pero' in C++
perche' gia' implementa alcuni containers come liste ad esempio (e
stringhe!).
Ecco come funziona il programma:
<OUTPUT>
Inserire il segmento: ponte rapida 15
Inserire il segmento: roccia inizio 5
Inserire il segmento: ponte roccia 19
Inserire il segmento: conca fine 17
Inserire il segmento: rapida conca 19
Inserire il segmento: X X 0
[inizio-roccia,5][roccia-ponte,19][ponte-rapida,15][rapida-conca,19][conca-f
ine,17]
</OUTPUT>
Ecco, il programma prende la sequenza di segmenti (che abbiamo usato qui nel
nostro esempio), la mette in una lista, poi incomnicia a costruire la lista
ordinata ed infine la stampa in ordine.
Credo fosse quello che voleva l'OP! Ovviamente anche l'implementazione C++
e' fatta solo per provare empiricamente l'algoritmo.... X X 0 per terminare
e' solo per andare di fretta ;-) (e tante altre carenze.... )
Volendo posso postare il codice C++, ma dubito che l'esercizio risulterebbe
utile.
Ora che l'OP sa un metodo (tra i piu' semplici) per implementarlo dovrebbe
impegnarsi da sola per risolvere il problema almeno in pratica!
Se l'OP avesse problemi nell'implementazione o a comprendere il
funzionamento dell'algoritmo allora saro' ben felice di rispondere.
A presto,
Tommy

 ;-)
beh dai, è divertente, spero di essere stato chiaro, ti lascio libertà per
implementarlo in C :))
saluti
Fabio

 [rapida-conca,19][conca-fine,17]
(che e' banale, si ottiene come descritto con 2 liste degli if e dei
clicli),
e' ancora piu' banale convertirla in una delle altre due forme, se richiesto
dall'esercizio, altrimenti puoi tenerlo cosi' come e'!
Per il secondo caso ad esempio basta scorrere la lista con un ciclo, e poi
un pezzo alla volta comporre l'altra lista con i dati che escono:
Leggiamo:
[inizio-roccia,5]
Scriviamo:
[inizio,0] <-> [roccia,5]
Leggiamo:
[roccia-ponte,19]
Scriviamo:
[inizio,0] <-> [roccia,5] <-> [ponte,24]  // 5+19
etc.... BANALE!
Tommy

Fare l'ipotesi semplificatrice che nel complesso la connessione tra città
costituisce una linea
ti allego la soluzione se vuoi darci un'occhiata, non è proprio ottimale,
alcune parti si potevano pensare meglio, ma ti assicuro che in 2 ore su
carta è stato gia' abbastanza duro tirare giu' questo! :P
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 20
#define INP "input.txt"    /* metti qui il tuo file di input */
typedef struct _city
{
 char c[LEN+1];
   struct _city *next;
} city;
typedef struct _citta
{
 char c1[LEN+1],c2[LEN+1];
 int d,flag,flag1;
 struct _citta *next,*next1,*next2;
 struct _giocatore *play;
} citta;
typedef struct _giocatore
{
 char nome[30],avversario[30];
 int ritardo;
 struct _giocatore *next;
} player;
citta *ordina(citta *);
void inserisci(char *,char *,citta *);
void elimina(char *,citta *);
void gioca(char *,char *,citta *);
void stampa(char *,citta *);
citta *identifica(char *,citta *);
void main ()
{
 FILE *fr;
 int i,n=0,d;
 citta *tmp,*prev=NULL,*primo,*primo1;
 char
c1[LEN+1],c2[LEN+1],giocatore[30],giocatore2[30],nodo[LEN+1],c,stringa[100];
 fr=fopen(INP,"r");
 if (!fr) exit (0);
 fscanf(fr,"%s%s%d",c1,c2,&d);
 while (!feof(fr))
 {
  tmp=(citta *)malloc(sizeof(citta));
  strcpy(tmp->c1,c1);
  strcpy(tmp->c2,c2);
  tmp->d=d;
      tmp->flag=0;
  tmp->next=NULL;
      tmp->play=NULL;
  tmp->next1=prev;
  prev=tmp;
  n++;
  fscanf(fr,"%s%s%d",c1,c2,&d);
 }
 fclose(fr);
 primo1=prev;
 primo=ordina(primo1);
 do
 {
  printf("> ");
  fgets(stringa,200,stdin);
  sscanf(stringa,"%c",&c);
  switch (c)
  {
   case 'A': sscanf(stringa,"%c%s%s",&c,giocatore,nodo);
     inserisci(giocatore,nodo,primo);
   break;
   case 'E': sscanf(stringa,"%c%s",&c,giocatore);
     elimina(giocatore,primo);
   break;
   case 'G': sscanf(stringa,"%c%s%s",&c,giocatore,giocatore2);
     gioca(giocatore,giocatore2,primo);
   break;
   case 'S': sscanf(stringa,"%c%s",&c,nodo);
     stampa(nodo,primo);
   break;
  }
 } while (c!='x');
}
citta *ordina (citta *p)
{
 citta *tmp,*tmpk;
   city *tmp2,*tmp3,*inizio=NULL,*prev;
   int flag,i;
   char a[30],b[30],s[2][30];
 tmp=p;
 /* inizio aggiunta
   anche city è una struttura aggiunta...
    */
    /* trovo la prima citta' mettendole in una lista.. se c'è già una città
    col nome x la cancello! così alla fine mi rimangono solo prima e ultima
    */
   while (tmp)
   {
    strcpy(s[0],tmp->c1);
    strcpy(s[1],tmp->c2);
      for (i=0;i<2;i++)
      {
       prev=tmp3=inizio;
         flag=1;
     while ((tmp3) && (flag))
       {
        if (!strcmp(tmp3->c,s[i]))
            {
               if (tmp3==inizio) inizio=tmp3->next;
               else prev->next=tmp3->next;
               free(tmp3);
               flag=0;
            }
    prev=tmp3;
          tmp3=tmp3->next;
       }
         if (flag)
         {
          tmp3=(city *)malloc(sizeof(city));
            strcpy(tmp3->c,s[i]);
            tmp3->next=NULL;
            if (prev) prev->next=tmp3;
          if (!inizio) inizio=tmp3;
         }
      }
  tmp=tmp->next1;
   }
 strcpy(b,inizio->c);
 /* partendo dalla prima citta' le giro in modo che il percorso sia ordinato
*/
 tmp=p;
 while (tmp)
   {
  tmp=p;
      while ((tmp) && ((strcmp(tmp->c1,b)) && (strcmp(tmp->c2,b)) ||
(tmp->flag)))
       tmp=tmp->next1;
      if (tmp)
      {
       tmp->flag=1;
       if (!strcmp(tmp->c2,b))
         {
          strcpy(a,tmp->c2);
          strcpy(tmp->c2,tmp->c1);
          strcpy(tmp->c1,a);
         }
         strcpy(b,tmp->c2);
      }
   }
   /* aggiungo un nodo, quello dell'ultima città */
   tmp=(citta *)malloc(sizeof(citta));
   strcpy(tmp->c1,inizio->next->c);
   strcpy(tmp->c2,"");
   tmp->next1=NULL;
   tmp->next=NULL;
   tmp->play=NULL;
   tmp->flag=0;
   tmp->d=0;
   tmpk=p;
   while (tmpk->next1)
    tmpk=tmpk->next1;
   tmpk->next1=tmp;
 tmp=p;
 /* fine aggiunta */
 while (tmp)
 {
  tmp->next=identifica(tmp->c2,p);
  tmp=tmp->next1;
 }
 return  identifica(inizio->c,p);
}
citta *identifica (char *s, citta *p)
{
 citta *tmp;
 tmp=p;
 while ((tmp) && (strcmp(s,tmp->c1)))
  tmp=tmp->next1;
 return tmp;
}
void inserisci (char *s1, char *s2,citta *p)
{
 citta *t;
 player *tmp,*tmp2;
 t=p;
 /* trovo il nodo interessato */
 while ((t) && strcmp(s2,t->c1))
  t=t->next;
 if (t)
 {
/* salvo in tmp il puntatore al primo giocatore */
  tmp=t->play;
  tmp2=(player *)malloc(sizeof(player));
  strcpy(tmp2->nome,s1);
  tmp2->ritardo=0;
/* aggiorno il puntatore del nuovo giocatore al primo giocatore vecchio */
  tmp2->next=tmp;
  strcpy(tmp2->avversario,"");
/* aggiorno il puntatore al primo giocatore */
  t->play=tmp2;
 }
}
void elimina (char *s1, citta *p)
{
 citta *tmp;
 player *tmp2,*tmp3,**prev;
 tmp=p;
 while (tmp)
 {
  tmp2=tmp->play;
  prev=&(tmp->play);
      tmp3=NULL;
  while (tmp2)
  {
       if (!strcmp(s1,tmp2->avversario)) strcpy(tmp2->avversario,"");
       if (!strcmp(s1,tmp2->nome))
          tmp3=tmp2;
   if (!tmp3) prev=&(tmp2->next);
   tmp2=tmp2->next;
  }
  if (tmp3)
   if (!strcmp(s1,tmp3->nome))
   {
    *prev=tmp3->next;
    free(tmp3);
   }
  tmp=tmp->next;
 }
}
void gioca (char *s1, char *s2, citta *p)
{
 char str[2][30];
 int flag=3,i,R=0;
 int* k[2];
 citta *tmp;
 player *tmp2;
 strcpy(str[0],s1);
 strcpy(str[1],s2);
 tmp=p;
 while ((tmp) && (flag))
 {
  tmp2=tmp->play;
  while(tmp2)
  {
   i=3;
   if (!strcmp(str[0],tmp2->nome)) i=0;
   if (!strcmp(str[1],tmp2->nome)) i=1;
   if (i!=3)
   {
    strcpy(tmp2->avversario,str[1-i]);
    flag-=(i+1);
    k[i]=&(tmp2->ritardo);
   }
   tmp2=tmp2->next;
  }
  if ((flag) && (flag<3)) R+=tmp->d;
  tmp=tmp->next;
 }
 *(k[0])=*(k[1])=R;
}
void stampa(char *s1, citta *p)
{
 citta *tmp;
 player *tmp2;
 tmp=p;
 while ((tmp) && (strcmp(s1,tmp->c1)))
  tmp=tmp->next;
 if (tmp)
 {
  tmp2=tmp->play;
  printf("Nodo %s:\n",s1);
  while (tmp2)
  {
   printf("%s ",tmp2->nome);
   if (strcmp(tmp2->avversario,""))
    printf("vs %s, delay %d ms",tmp2->avversario,tmp2->ritardo);
   printf("\n");
   tmp2=tmp2->next;
  }
 }
}

 ;-)
siam qui apposta :)
(ti assicuro che la prova in questione ha segato molta gente)

 Che ne dite?
così mi sembra molto laborioso (se ho capito bene quello che intendi).
Nel frattempo mi è venuto in mente 1 altro metodo piu' semplice, giocando
con "testa" e "coda" del fiume.
Ti posto parti della bozza che ho pensato (ho supposto di avere un array e
che i nomi dei punti fossero char)
struct segment {
char p1;
char p2;
int distanza;
int position;   // identifica l'ordine, va inizializzato a -99 ad esempio
};
suppongo poi di avere un array contenente queste strutture, di dimensione
arraylen e due variabili intere, testapos e codapos, entrambe uguali per
adesso a 0. Prendo il primo elemento dell'array, imposto 
p1 come testa e p2 come coda e position=0. 
Scorro poi l'array alla ricerca prima del carattere che identifica testa,
quando lo trovo la nuova testa sarà l'altro carattere presente nella struct
(in alcuni casi dovro' invertire i record nella struttura). Decremento
testapos e assegno questo valore al campo position della struct.
Faccio le medesime cose per la coda (solo che questa volta incrementero'
codapos invece di decrementarlo).
Piu' o meno salta fuori una cosa tipo:
for (a=1;a<=arraylen;a++) {
 tmp=findtesta(testa);
 if (tmp!=-1) {
        if (array[tmp].p1==testa) {
                array[tmp].p1=array[tmp].p2; array[tmp].p2=testa;
                testa=array[tmp].p1;
        } else testa=array[tmp].p1;
        testapos--;
        array[tmp].position=testapos;
 }
 tmp=findcoda(coda);
 if (tmp!=-1) {
        if (array[tmp].p2==coda) {
                array[tmp].p2=array[tmp].p1; array[tmp].p1=coda;
                coda=array[tmp].p2;
        } else coda=array[tmp].p2;
        codapos++;
        array[tmp].position=codapos;
 }
}
L'unica cosa significativa di findcoda è che non valuta i record che hanno
position!=99 (poichè sono già stati valutati precedentemente)
In questo modo avro' l'array con i campi position delle struct "ordinati",
ad esempio
- -2 -1 0 1 2 3 4.
Nel caso di un array posso costruirne subito 1 altro ordinato secondo i
campi position e a questo punto trovare le distanze sarà quasi banale.
Ciao
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/GYkJQb6qi6QXZLkRAvavAJ9DXZ1O9XIEtEnvhOr/+eqg9NUDbgCfWVDl
6zPeamIpTPoyHpnJCPhWpnY=
=/fTr
-----END PGP SIGNATURE-----

ti spiego anche un attimo come funziona l'algoritmo che magari è utile !
inizialmente non mi ero accorto che gli archi del grafo potessero non essere
ordinati tutti nello stesso verso...
così avevo solamente aggiunto un puntatore next alla struttura che la ordiva
per percorrenza.
(next1 la ordina per come ha letto i dati nel file)
percio' ho dobuto aggiungere una funzione che trovasse la prima città (una
delle due) e partendo da quella esaminasse tutti gli altri archi ordinandoli
nella percorrenza prescelta...
il mio programma quindi ordina la lista una volta e poi è facilitato nel
calcolo delle distanze...
altri hanno usato un doppio puntatore prec e next in modo da salvare la
città prima e quella dopo (una città DOVEVA stare in una struttura in prec e
in un'altra in next, in questo modo ti assicuravi la percorrenza)
altri ancora non hanno ordinato gli archi... andando tutte le volte che si
apriva una partita a visitare il percorso... soluzione forse meno
incasinata, ma meno bella...
ciao

 position!=99 (poichè sono già stati valutati precedentemente)
qui intendevo dire "L'unica cosa significativa di findtesta e findcoda è che
non valutano i record che hanno position!=-99"...
Ciao
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/GZQvQb6qi6QXZLkRAuOxAJ97D84BRGIrR4p96UQsgUyfYQOUUgCfdLek
C/AksuZnFdllVa5+02cP0pg=
=n4Q3
-----END PGP SIGNATURE-----