Salve a tutti mi trovo in seria difficoltà in un implemetazione in java di un problema. il testo è il seguente:
Una formichina deve cambiare formicaio trasportando con sé delle briciole di pane. Durante il
tragitto ci sono tratti di percorso lungo i quali si trovano briciole da aggiungere a quelle che già
si stanno trasportando, mentre in altri tratti più complicati alcune briciole cadono e si perdono
definitivamente. Il formicaio di partenza ha tanti possibili punti di uscita, ed il formicaio di
arrivo ha tanti possibili ingressi. Bisogna trovare il percorso più appropriato da un punto di
uscita del formicaio di partenza, ad un qualsiasi punto di ingresso del formicaio di arrivo, che sia
complessivamente il più vantaggioso per quanto riguarda il trasporto delle briciole. I possibili tratti
percorribili vengono rappresentati tramite un grafo orientato pesato dove i pesi sono numeri interi:
positivi quando indicano briciole che si perdono lungo il tragitto, negativi quando invece le briciole
si acquisiscono. Alcuni nodi del grafo indicano possibili punti di uscita dal formicaio di partenza,
alcuni altri indicano invece possibili punti di ingresso nel formicaio di arrivo.
L’input del problema è codificato come segue:
N M
X Y
x_i y_j m_1
x_k y_l m_2
Nella prima riga due numeri interi N ed M, corrispondenti rispettivamente al numero di nodi e di
archi del grafo. I nodi sono numerati da 0 a N-1. Nella seconda riga ci sono due numeri X e Y: i
nodi da 0 a X (estremi inclusi) sono nodi corrispondenti ad uscite del formicaio di partenza, mentre
i nodi da Y a N-1 (estremi inclusi) sono possibili nodi di ingresso nel formicaio di arrivo. Ci sono
poi restanti M righe, ognuna contenente tre numeri rappresentanti un arco: il nodo sorgente, il
nodo destinazione, ed il peso (un intero, possibilmente negativo). Il file di output deve contenere il
cammino migliore che permette alla formichina da spostarsi dal formicaio di partenza al formicaio
di arrivo. Inserire nel file il solo valore -1 se un tale percorso ottimale non esiste. Un esempio di
output con il percorso migliore è il seguente:
i
j
k
dove i, j e k sono i 3 nodi da percorrere per ottenere il percorso migliore.
(Scusate per la lunghezza del messaggio ma volevo essere il piu chiaro possibile.)
Grazie mille per la vostra collaborazione