Bitocja OIG

0

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.

0

Problem rozwiazany.
Zadanie nie jest dosc doprecyzowane. Niby mamy autostrady dwukierunkowe i w opracowaniu pisze ze graf nieskierowany , natomiast w niektorych testach moga pojawic sie krawedzie z roznymi wagami w obie strony typu

6 -> 8 z waga 3
8 -> 6 z waga 25

Wtedy trzeba w odpowiedni kierunek brac mniejsza wage.
Przy Dijkstrze na listach to nie ma znaczenia, ale w FW jak tylko jedna liczba siedzi no to niestety ma.

1 użytkowników online, w tym zalogowanych: 0, gości: 1