There is a problem with the prim function. A segmentation fault I guess. Please help me with this. I have tried a lot now. s is the starting vertex which actually doesn't matter. arr is a 2D array that stores weights. V is a 2D array that stores adjacent edges. check array stores min distances. visit stores visited nodes.
#define INF 99999;
typedef long int ull;
bool visit[3000]={false};
vector<ull>check(3000,0);
void prim(ull in,vector<ull>V[],ull **arr)
{
ull i;
visit[in]=true;
for(i=0;i<V[in].size();i++)
{
if(!visit[V[in][i]])
{
check[V[in][i]]=min(check[V[in][i]],arr[in][V[in][i]]);
}
}
check[in]=INF;
}
void solve()
{
ull i,j,n,e,s,u,v,w;
cin>>n>>e;
vector<ull>V[n];
ull **arr=new ull*[n];
for(i=0;i<n;i++)
{
arr[i]=new ull[n];
}
for(i=0;i<n;i++)
{
check[i]=INF;
}
for(i=0;i<e;i++)
{
cin>>u>>v>>w;
u--;
v--;
arr[u][v]=w;
arr[v][u]=w;
V[u].push_back(v);
V[v].push_back(u);
}
cin>>s;
s--;
ull ind,ad=0;
check[s]=0;
for(i=0;i<n;i++)
{
auto it=min_element(check.begin(),check.end());
ad+=check[it-check.begin()];
ind=(it-check.begin());
prim(ind,V,arr);
}
cout<<ad<<"\n";
}
Aucun commentaire:
Enregistrer un commentaire