# Algorithm is on the contact box. Where's the mistake?

• Trying to:

http://informatics.mccme.ru/mod/statements/view3.php?id=261&chapterid=185

We need to take the length of all the ribs of the mine. I'm writing straight for m log(n).

The count is tied to a list of related things. Where's the mistake?

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(false);
int n,m;//кол-во вершин, кол-во ребер
cin >> n >> m;
vector< vector< pair<int,int> > >v(n);
for(int i=0;i<m;++i){//список смежности
int v1,v2,weight;//вершина1, вершина2, вес ребра между ними(длина)
cin >> v1 >> v2 >> weight;
v[v1-1].push_back(make_pair(v2-1,weight));
v[v2-1].push_back(make_pair(v1-1,weight));
}
set< pair<int,int> > u; //обход (длина=dl, вершина)
vector<int> dl(n,-1); //длина от остова до вершин.
//стартуем с 0
dl=0;
u.insert(make_pair(0,0));
int result = 0; //длина всех ребер мин остова
while(!u.empty()){ //обход за n log(m)
int k = u.begin()->second;
result += u.begin()->first;//добавляем длину
u.erase(u.begin());
for(int j=0;j&lt;v[k].size();++j){
int i=v[k][j].first, len=v[k][j].second;
if(dl[i]==-1 || dl[i]&gt;len){
u.erase(make_pair(dl[i],i));
dl[i] = len;
u.insert(make_pair(dl[i],i));
}
}
}
cout&lt;&lt;result;
return 0;

}


• This is working Algorithm Prima for n log(m):

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(false);
int n,m;//кол-во вершин, кол-во ребер
cin >> n >> m;
vector< vector< pair<int,int> > >v(n);
for(int i=0;i<m;++i){//список смежности
int v1,v2,weight;//вершина1, вершина2, вес ребра между ними(длина)
cin >> v1 >> v2 >> weight;
v[v1-1].push_back(make_pair(v2-1,weight));
v[v2-1].push_back(make_pair(v1-1,weight));
}
set< pair<int,int> > u; //обход (длина=dl, вершина)
vector<int> dl(n,-1); //длина от остова до вершин.
vector<int> used(n);
//стартуем с 0
dl=0;
u.insert(make_pair(0,0));
int result = 0; //длина всех ребер мин остова
while(!u.empty()){ //обход за n log(m)
int k = u.begin()->second;
result += u.begin()->first;//добавляем длину
u.erase(u.begin());
used[k]=1;
for(int j=0;j<v[k].size();++j){
int i=v[k][j].first, len=v[k][j].second;
if(!used[i] && (dl[i]==-1 || dl[i]>len)){
u.erase(make_pair(dl[i],i));
dl[i] = len;
u.insert(make_pair(dl[i],i));
}
}
}
cout<<result;
return 0;
}


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2