Sunnydale

Sunnydale è una città che – per ragioni storiche e ambientali – ospita un elevatissimo numero di vampiri.

Per ragioni cutanee i vampiri non possono sopportare la luce solare e, storicamente, hanno sempre avuto enormi difficoltà a viaggiare col sole alto nel cielo; l’attraversamento delle gallerie sotterranee di Sunnydale è sempre stato il mezzo preferito dai vampiri per muoversi nella città.

I continui crolli delle gallerie hanno creato dei fori nei soffitti, rendendone alcune troppo luminose per un attraversamento tranquillo e sereno.

Harmony, una ragazza-vampiro, passeggia per le gallerie di Sunnydale quando il suo amico Spike le telefona per invitarla a casa sua.

Purtroppo ella si muove per le gallerie sotterranee secondo una regola tanto semplice quanto tassativa: ad ogni svincolo sceglie sempre e comunque la galleria meno luminosa per paura di rovinare la propria pelle.

Sapendo che non esistono due gallerie egualmente luminose, bisogna determinare se Harmony possa raggiungere la casa sotterranea di Spike e, in caso affermativo, quante gallerie le sono necessarie per arrivare.

Dati di input

La prima riga del file input.txt è composta da quattro numeri interi N, M, H e S:

  • il primo rappresenta il numero degli svincoli (numerati da 1 a N),
  • il secondo rappresenta il numero delle gallerie,
  • il terzo rappresenta l’indice dello svincolo in cui si trova Harmony quando riceve la telefonata;
  • il quarto, infine, rappresenta l’indice dello svincolo della casa di Spike.

Ognuna delle successive M righe descrive una galleria e contiene tre numeri interi A, B e L separati da uno spazio: i primi due rappresentano gli svincoli collegati dalla galleria mentre il terzo rappresenta il suo grado di luminosità.

Dati di output

Il file output.txt dovrà contenere un unico numero intero:

  • -1 se Harmony non riuscirà a raggiungere Spike;
  • altrimenti, il numero di gallerie che ella percorrerà prima di raggiungerlo.

Assunzioni

  • 2 ≤ N ≤ 50000
  • 1 ≤ M ≤ 50000
  • Non esistono due gallerie con la stessa luminosità L
  • Per ogni galleria, 1 ≤ L ≤ M
  • 1 ≤ H, S ≤ N.

Esempi di input/output

input.txt output.txt
5 6 1 5
1 2 5
2 3 1
3 4 3
4 5 2
5 1 6
1 4 4
2
3 2 2 1
3 1 2
2 3 1
-1

/*
	www.valcon.it
	OII 2005 - Fase territoriale - Sunnydale
*/
#include
#include

using namespace std;

#define NMAX 50000
#define MMAX 50000
#define LMAX 50000

long destinazioni[NMAX+1];
long luminosita  [NMAX+1];

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	long Nsvincoli, Mgallerie, Harmony, Spike;
	
	fin >> Nsvincoli >> Mgallerie >> Harmony >> Spike;	
	
	for(long i=1; i <= Nsvincoli; i++) 
	{
		destinazioni[i]=0;
	    luminosita[i]  =LMAX+1;
    }

	long A, B, L;
	for(long i=1; i <= Mgallerie; i++)
	{
		fin >> A >> B >> L;
		
		if(L < luminosita[A]) { luminosita[A]=L; destinazioni[A]=B; }
		if(L < luminosita[B]) { luminosita[B]=L; destinazioni[B]=A;	}
    }
    
	long lunghezza=0;
	long prossima;
	while(Harmony && Harmony != Spike)
	{
		lunghezza++;
		
		prossima=destinazioni[Harmony];
		destinazioni[Harmony]=0;
		Harmony=prossima;
	}
	
	if(Harmony == Spike) fout << lunghezza;
	else                 fout << "-1";
}