Distanze

Antonio è in viaggio, e ha una tabella di distanze tra città.
Su di essa, purtroppo, non compare la distanza tra la sua città di partenza e quella di arrivo, per raggiungere la quale bisogna passare per altre città intermedie.
Dovete aiutare Antonio a trovare la distanza relativa al percorso più breve tra la città di partenza e quella di arrivo desumibile dalla tabella.

Dati in input

Il file input.txt è costituito da una prima riga nella quale sono indicati, separati da un carattere spazio, il numero totale di città in tabella N e il numero di distanze mutue tra due città D.
Seguono D righe, ciascuna delle quali contiene gli identificatori numerici delle due città e la loro mutua distanza, separati da un carattere spazio.

Dati in output

Il programma, dopo aver letto il file di input, deve calcolare la distanza minima tra la città di partenza e quella di arrivo, e scriverla su un file di nome output.txt.
Più precisamente, il file output.txt deve essere costituito da una sola riga, contenente un numero intero che rappresenta la distanza più breve tra la città di partenza e quella di arrivo.

Assunzioni

1. Il numero N di città è inferiore a 1000
2. Il numero di distanze è D inferiore a 10000
3. Gli identificatori delle città sono interi compresi tra 1 e N.
4. La città di partenza e la destinazione sono sempre associate agli identificatori 1 e 2, rispettivamente.

Esempi di input/output

/*
    wwww.valcon.it
    OII 2001 - Olimpiadi nazionali - DISTANZE
*/

#include 
#include 
#include 
#include 
using namespace std;

#define NMAX         1000	// n. massimo di città
#define PARTENZA     1      // la città di partenza   
#define DESTINAZIONE 2      // la città destinazione
#define INFINITA     -1     // la distanza delle città non visitate

struct INFO  { int dest, dist; };     // una destinazione con distanza
vector citta[NMAX+1];           // le città con i collegamenti
int          distanze[NMAX+1];        // la distanza minima per ogni città
queue   visitare;                // la coda delle città da visitare

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
    int N,   // numero di città
        D;   // numero di collegamenti

    fin >> N >> D;    
    int partenza, 
	    destinazione,
	    distanza;       
    for(int i=1; i <= D; i++)
    {    	
	    fin >> partenza >> destinazione >> distanza;
	    INFO info;
	    info.dist=distanza;
		info.dest=destinazione; citta[partenza    ].push_back(info);
	    info.dest=partenza;  	citta[destinazione].push_back(info);
    }    	
    for(int i=1; i <= N; i++)		// tutte le città hanno distanza infinita
    	distanze[i]=INFINITA;
    distanze[PARTENZA]=0;           // tranne quella di partenza

	/*                                                 DEBUG
	for(int i=1; i <= N; i++)
	{
		for(int j=0; j < citta[i].size(); j++)
			cout << i << '-' << citta[i][j].dest << ": " << citta[i][j].dist << endl;
	}	
	for(int i=1; i <= N; i++)
    	cout << distanze[i] << ' ';	
	*/
	
    visitare.push(PARTENZA);	           // comincia con la città di partenza
    do
    {
    	partenza=visitare.front();         // preleva una città da visitare 
		visitare.pop();	  
        for(int i=0; i < citta[partenza].size(); i++)   // per ogni collegamento
	    {
            destinazione=citta[partenza][i].dest;
            distanza    =citta[partenza][i].dist;
                                                        // se è da visitare...
   		 	if(distanze[destinazione] == INFINITA                   || 
			   distanze[destinazione] >  distanze[partenza]+distanza )		   	
		 	{
				distanze[destinazione]=distanze[partenza]+distanza;  // aggiorna la distanza
				visitare.push(destinazione);                         // è da visitare
		 	}
 	    }
    } while(!visitare.empty());           // finché ci sono città da visitare
        
    fout << distanze[DESTINAZIONE];       // la distanza minima della destinazione
    return 0;
}