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]=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]=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;
    }




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2