Wszystkie możliwe drogi.

Odpowiedz Nowy wątek
2011-10-08 11:56
0

Witam!

Mam problem z zadaniem, w którym muszę wypisać ilość możliwych dróg. Szczerze mówiąc, nie wiem nawet, jak się za to zabrać dopiero od tygodnia piszę w c++, wcześniej tylko PHP i RAMmachine. Na wejściu mamy x=ilości miast (miasta 1, 2, 3, ... , (x-1), x), y=ilości dróg, a później y dróg jednokierunkowych n m (z miasta n do miasta m). Między miastami może być więcej niż jedna droga. Wyjście to ilość możliwości dotarcia z miasta 1 do miasta 2, dla nieskończonej wypisujemy inf. Dróg można używać wielokrotnie. Czy moglibyście mi pomóc?

Przykład wejścia:

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


mysle, ze to, ze dopiero od tygodnia piszesz w C++ nie jest tutaj najwiekszym problemem... - icek 2011-10-08 12:40
Nie, to nie jest największy problem. Największym problemem jest to, że nie wiem jak to zrobić... - merlinnot 2011-10-08 12:45

Pozostało 580 znaków

2011-10-08 12:53
0

Teoria grafów: graf skierowany, szukanie ilości ścieżek z wierzchołka A do B.


Pozostało 580 znaków

2011-10-08 12:54
0

Algorytmy grafowe.


Zero litości dla nieróbstwa.

Pozostało 580 znaków

2011-10-08 15:26
0

Ok, znalazłem niezłego pdf-a, z którego przynajmniej coś rozumiem. Chciałem na początku stworzyć tablicę dwuwymiarową miasto*miasto, wyzerować ją i w pola w których jest droga wpisać ilość dróg. Nie mogę sobie poradzić z zerowaniem. Mój kod:
EDIT: zmieniłem to:


    do
        {
        do
            {
            ttwod[i][j]=0;
            j=j+1;
            }
            while (j==(!(lmiast+1)));

na to co jest w następnym poście. Zapomniałem o zmianie wartości drugiej zmiennej w pierwszym while'u.


edytowany 1x, ostatnio: merlinnot, 2011-10-08 20:47

Pozostało 580 znaków

2011-10-08 18:35
0

Dobra, poradziłem sobie :)
Teraz kod wygląda tak:

#include <iostream>
using namespace std;
int main() {
    int lmiast, ldrog;
    cin >> lmiast;
    cin >> ldrog;
    int zmiasta, domiasta, x, y;
    int ttwod[(lmiast+1)][(lmiast+1)];
    x=0;
    y=0;
    while (!(x==(lmiast)))
        {
        y=0;
        while (!(y==(lmiast)))
            {
            ttwod[x][y]=0;
            y=y+1;
            }
        x=x+1;  
        } 
        x=(0);
    for (x=0; (!(x==ldrog)); x=x+1)
        {
        cin >> zmiasta;
        cin >> domiasta;
        ttwod[zmiasta][domiasta]=(ttwod[zmiasta][domiasta]+1);
        }
/* KONIEC TABLICY. CO DALEJ? */
}

Rozumiem, że dalej trzeba zastosować jakąś metodę poszukiwania ścieżek. Jaką według Was powinienem zastosować (albo przynajmniej spróbować:))?


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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