Witam. Czy mógłbym prosić Was o ocenę programu? W porównaniu z podanymi odpowiedziami w poleceniu, jest jedna różnica w moich odpowiedziach. W 3 linijce Out.txt, wypisuje 6(1), zamiast 6(5). Ale nie wiem, gdzie szukać błędu.
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
using namespace std;
#define MAXINT 1000000;
struct wierzcholki
{
vector < int >polaczenia;
vector < int >wagi;
} *Lista;
class Forda_Bellmana
{
public:
int *dist;
public:
void Algorytm (int ile_wierzcholki)
{
dist = new int[ile_wierzcholki + 1];
for (int i = 0; i < ile_wierzcholki + 1; i++)
{
dist[i] = MAXINT;
}
dist[0] = 0;
for (int k = 0; k < ile_wierzcholki - 1; k++)
{
for (int i = 0; i < ile_wierzcholki + 1; i++)
{
for (int j = 0; j < Lista[i].polaczenia.size (); j++)
{
if (dist[Lista[i].polaczenia[j]] > dist[i] + Lista[i].wagi[j])
{
dist[Lista[i].polaczenia[j]] = dist[i] + Lista[i].wagi[j];
}
}
}
}
for (int j = 0; j < ile_wierzcholki + 1; j++)
{
}
}
};
class Dijkstry
{
public:
int *dist;
int *pred;
int min (int *_dist, bool * _tabB, int ileW)
{
int min = MAXINT;
int gdzie_min = 0;
for (int i = 0; i < ileW; i++)
{
if (!_tabB[i] && _dist[i] <= min)
{
min = _dist[i];
gdzie_min = i;
}
}
return gdzie_min;
}
void Dijkstra (int ileW, int **tablica, int Wdocelowy)
{
dist = new int[ileW];
pred = new int[ileW];
bool *tabB = new bool[ileW];
for (int i = 0; i < ileW; i++)
{
dist[i] = MAXINT;
pred[i] = -1;
tabB[i] = false;
}
dist[Wdocelowy - 1] = 0;
pred[Wdocelowy - 1] = -1;
for (int j = 0; j < ileW; j++)
{
int u = min (dist, tabB, ileW);
tabB[u] = true;
for (int v = 0; v < ileW; v++)
{
if (!tabB[v])
{
if (tablica[u][v] != 214748000 && tablica[u][v] != -1)
{
if (dist[u] != 214748000)
{
if (dist[u] + tablica[u][v] < dist[v])
{
dist[v] = dist[u] + tablica[u][v];
pred[v] = u + 1;
}
}
}
}
}
}
}
};
int
main ()
{
fstream plik;
int n;
plik.open ("In.txt", ios::in);
if (plik.good () == false)
{
cout << "nie otwiera sie plik ";
return 1;
}
plik >> n;
Lista = new wierzcholki[n + 1];
string lin;
char pom;
getline (plik, lin);
int indeks = 1, liczba;
while (getline (plik, lin))
{
istringstream zmienna (lin);
while (zmienna >> liczba)
{
Lista[indeks].polaczenia.push_back (liczba);
zmienna >> pom;
zmienna >> liczba;
zmienna >> pom;
Lista[indeks].wagi.push_back (liczba);
}
indeks++;
}
plik.close ();
for (int i = 0; i < n; i++)
{
Lista[0].polaczenia.push_back (i + 1);
Lista[0].wagi.push_back (0);
}
Forda_Bellmana ford;
ford.Algorytm (n);
int **tabb = new int *[n];
for (int i = 0; i < n; i++)
{
tabb[i] = new int[n];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tabb[i][j] = MAXINT;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < Lista[i + 1].polaczenia.size (); j++)
{
tabb[i][Lista[i + 1].polaczenia[j] - 1] =
Lista[i + 1].wagi[j] + ford.dist[i + 1] -
ford.dist[Lista[i + 1].polaczenia[j]];
}
}
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
}
}
Dijkstry tab[n];
for (int i = 0; i < n; i++)
{
tab[i].Dijkstra (n, tabb, i + 1);
}
int tabD[n][n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tabD[i][j] = tab[i].dist[j] + ford.dist[j + 1] - ford.dist[i + 1];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
}
}
plik.open ("Out.txt", ios::out);
if (plik.good () == false)
{
cout << "nie otwiera sie plik ";
return 1;
}
for (int i = 0; i < n + 1; i++)
{
plik << ford.dist[i] << " ";
}
plik << endl;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < Lista[j].polaczenia.size (); i++)
{
plik << Lista[j].polaczenia[i] << "(" << Lista[j].wagi[i] +
ford.dist[j] - ford.dist[Lista[j].polaczenia[i]] << ") ";
}
plik << endl;
}
for (int i = 0; i < n; i++)
{
plik << "Delta^[" << i + 1 << "][";
for (int j = 0; j < n; j++)
{
plik << tab[i].dist[j] << " ";
}
plik << "],D[" << i + 1 << "][";
for (int j = 0; j < n; j++)
{
plik << tabD[i][j] << " ";
}
plik << "]" << endl;
}
plik.close ();
return 0;
}