Zadanie Wielka Ucieczka Traktorem

[jedrzejd]

Witam wiem, że te zadanie Tutaj jest nie stąd, ale na innych forach mi nikt nie pomógł .
Prosiłbym bardzo o pomoc.
Wiem że trzeba puścić algorytm Dijkstry z 1 wierzchołka.
O to jest kod
http://ideone.com/QO9hXj
Z góry dziekuje

[mariusz193]

dla danych przykładowych z zadania daje dobry wynik - więc jakiej pomocy oczekujesz ?

[jedrzejd]

I na tym się kończy poprawne odp.
Dostaje 63 punkty

[mariusz193]

w zasadzie nie powinienem pomagać (ze względu na cel), ale ponieważ po dokładnym obejrzeniu programu nie stwierdzam większych błędów - istotne to (nieumiejętne) użycie pair zamiast własnej struktury (gdybyś użył własnej struktury, prawdopodobnie uniknąłbyś błędu ), potem to już mnie istotne optymalizacja, wielkość tablic, przejrzystość programu

zastanów się nad wynikiem dla takich danych:

5 5
1 2 1
2 3 1
3 4 1
4 1 1
1 5 20

[jedrzejd]

Graf
1
5
to zle?

istotne to (nieumiejętne) użycie pair zamiast własnej struktury (gdybyś użył własnej struktury, prawdopodobnie uniknąłbyś błędu ), potem to już mnie istotne optymalizacja, wielkość tablic, przejrzystość programu

to znaczy ze pary psują program?

[mariusz193]

podałem zły przykład - pomyliłem się przy wpisywaniu danych, ale otrzymałem oczekiwany rezultat
i nie sprawdziłem danych, a przekopiowałem

chciałem znaleźć przykład taki,który ujawni błąd a nie pisać na czym polega - a teraz dalej szukam właściwego przykładu

[jedrzejd]

czyli wiesz jaki to bład

[mariusz193]

mam nadzieję, że teraz podaję poprawny przykład danych pokazujący niepoprawne działanie programu

6 6
1 2 5
2 3 5
3 4 5
1 5 6
5 4 6
4 6 1

[jedrzejd]

Dzięki dało wreście accept kod prawie sie nie zmienił . Wywaliłem tylko tablice odwiedzonych dla dijkstry.
Choć sam nie wiem zbytnio czemu to psulo program ale dobra :).
Jeszcze raz dzieki .

[mariusz193]

rzeczywiście, usunięcie tablicy odwiedzonych poprawia wynik - ale jest niepoprawne, bo jedynie maskuje błąd a nie usuwa, zaś przy poprawnych testach wydajnościowych byłoby przekroczenie czasu.

po analizie podanego przykładu (+poprzednia wiadomość priv) powinieneś bez problemu znaleźć prawdziwy błąd

[jedrzejd]

chociaż to dziwne ale te pary powinny dzialac poprawnie bo kolejka piorytetowa sortuje domyslnie je malejoco a powinna rosnaco wiec wrzucam ujemne wartosci (i domysnie po pierwszej czesci pary chyba).

[mariusz193]

tylko jaką ujemną wartość tam wrzucasz - tak właśnie mszczą się wszystkie obejścia problemów gdy chce się coś zrobić łatwo a nie w sposób właściwy

gdybyś zdefiniował własną funkcję porównującą lub zdefiniował własną strukturę (i wtedy też funkcję) to prawdopodobnie wstawiałbyś poprawną wartość

[jedrzejd]

for(int i=0;i<tablica[index].size();++i){
int t1 = tablica[index][i].first;//waga
int t2 = tablica[index][i].second;//wierzcholek
printf("%d ",t1);
if(odleglosc[t2]>odleglosc[index]+t1){
odleglosc[t2]=odleglosc[index]+t1;
kolejka.push(make_pair((-t1),t2));//sortuje po wadze
}
}

sorry za formatowanie kodu ale na spoju jest troche dziwne

[mariusz193]

zacznij myśleć

odpowiedź poszła na priv