Mam nadzieje, że trafiłem w dobry dział - nie mogę rozpracować tego zadania.
http://www.main.edu.pl/user.phtml?op=showtask&task=bit&con=OIG1
Korzystam z opisu algorytmu:
http://www.oi.edu.pl/html/zadania/oig1/Etap3/bit.pdf
Problem jest taki ze nie moge sie przebic powyzej 33 punktow / 100.
Ogolny problem: po zapuszczeniu Floyda-Warshalla mozemy dodawac krawedzie. Jesli najkrotsza sciezka od 1 -> n po dolozeniu krawedzi bedzie lepsza niz aktualna, to ja dokladamy i aktualizujemy sciezki wpp nie dokladamy i rozpatrujemy kolejna propozycje:
int aktualizujOdleglosci(TAB &d, int x, int y, int waga)
{
int n = d.size()-1;
int aktWynik = d[1][n];
bool wynik = false;
int nowy1 = d[1][x] + waga + d[y][n];
int nowy2 = d[1][y] + waga + d[x][n];
if(nowy1 < aktWynik || nowy2 < aktWynik) {
wynik = true;
}
// jak sie nie udalo to nic nie robimy
if(!wynik)
return false;
// udalo sie
// teraz niby dodajemy te krawedz do grafu i aktualizujemy
// odleglosci
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][x] + waga + d[y][j]);
d[i][j] = min(d[i][j], d[i][y] + waga + d[x][j]);
}
return true;
}
Robie niby tak jak kaza.
Policzylem najkrotsze sciezki FW. Przychodzi krawedz (x,y) o wadze "waga" :-)
Patrze czy idac ta krawedzia od 1->n moge uzyskac lepszy czas. Jesli moge to
powinienem dodac krawedz do grafu, ale operuje juz na macierzy wag wiec po prostu ja wliczam.
To nie jest kwestia przepelnienia czy innych tego typu rzeczy.
Cos musi mi umykac, cos musze robic zle w tej funkcji.
Moze ktos pomoc?
Czyli zadanie glownie sprowadza sie do aktualizacji macierzy wag po dodaniu nowej krawedzi w czasie kwadratowym.
Dzieki za pomoc.