Witam,
Mam pewnie problem. Otóż napisałem sobie program do zliczania ścieżek przejścia z wierzchołka A do B i nie zawsze działa jak powinien.
Otóż problem jest tego typu, że wierzchołek docelowy jest jeden, natomiast źródłowych jest kilka (tablica) i dla każdego takiego wierzchołka od nowa zapuszczam sobie funkcję. Na samym końcu trzeba podać sumę kosztów przejścia z wierzchołków źródłowych do docelowego, ale nie zliczać 2 razy tych samych krawędzie. Czyli na przykład przy pierwszym wywołaniu funkcji ścieżka wygląda: A -> B -> C, a przy drugim D -> B -> C to ścieżki B -> C (jej kosztu) nie zliczamy 2 razy.
Mój kod poniżej, będę wdzięczny za jakąś wskazówkę, albo wskazanie błędu.
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
using namespace std;
typedef vector<vector<pair<int,int> > > Graph;
class Comparator
{
public:
int operator() ( const pair<int,int>& p1, const pair<int,int> &p2)
{
return p1.second>p2.second;
}
};
int dijkstra(const Graph &G,const int source,const int &destination, bool *czyOdwiedzony)
{
vector<int> d(G.size());
for(unsigned int i = 0 ;i < G.size(); i++)
{
d[i] = 2000000;
}
int min,a;
int wynik = 0;
priority_queue<pair<int,int>, vector<pair<int,int> >, Comparator> Q;
d[source] = 0;
Q.push(make_pair(source,d[source]));
while(!Q.empty())
{
int u = Q.top().first;
if(u==destination) break;
Q.pop();
min=2000000;
for(unsigned int i=0; i < G[u].size(); i++)
{
int v= G[u][i].first;
int w = G[u][i].second;
if(d[v] > d[u]+w)
{
d[v] = d[u]+w;
if(min >= d[v])
{
min=d[v];
a=v;
}
Q.push(make_pair(v,d[v]));
}
}
if(czyOdwiedzony[a] == true)
{
wynik+=d[a];
czyOdwiedzony[source] = true;
return wynik;
}
czyOdwiedzony[a] = true;
}
czyOdwiedzony[source] = true;
wynik+=d[a];
return wynik;
}
int main()
{
ios_base::sync_with_stdio(0);
int n,m,s,info;
int v1,v2,w1,w2;
cin>>n>>m;
Graph g;
g.resize(n);
for(int i=0; i<m; i++)
{
cin>>v1>>v2>>w1>>w2;
g[v1].push_back(make_pair(v2,w1));
g[v2].push_back(make_pair(v1,w2));
}
cin>>s;
int inform[s];
for(int i=0; i<s; i++)
{
cin>>inform[i];
}
cin>>info;
bool czyOdwiedzony[m];
for(int i=0;i<m;i++)
czyOdwiedzony[i] = false;
int wynik =0;
for(int i=0; i<s; i++)
{
wynik += dijkstra(g,inform[i],info,czyOdwiedzony);
}
cout<<wynik<<endl;
return 0;
}
Pozdrawiam