Пытаюсь сдать задачу:
http://informatics.mccme.ru/mod/statements/view3.php?id=261&chapterid=185
Надо вывести длину всех ребер мин. остова. Пишу сразу за m log(n).
Граф связный задан списком смежности. Где же ошибка?
#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<v[k].size();++j){
int i=v[k][j].first, len=v[k][j].second;
if(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;
}