1. Пользуйтесь тегами кода. - [code] ... [/code] 2. Точно указывайте язык, название и версию компилятора (интерпретатора). 3. Название темы должно быть информативным. В описании темы указываем язык!!!
А можно ли в priority_queue (ну и в ее подобных) в критерие сортировки указать (если равно чему-то то не соритровать)? Например, мне нужно сформировать heap, но чтобы первый элемент не был равен X.
P.S. И вот еще такой вопрос созрел: можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как, и как потом с этим работать?
Погоди. Что значит, если элемент равен чему-то, то "не сортировать"? Не заноси этот элемент в очередь, если он равен X и все. Допустим, занес ты элемент в очередь, и сейчас метод top() должен его вернуть. Что будем делать? Ничего не возвращать? Вытащим этот элемент из начала очередь и засунем опять в конец?
В принципе, можно написать свой критерий сортировки, и создать priority_queue именно с ним, но тогда нужно точно знать ответы на те вопросы, которые я задал...
Допустим, занес ты элемент в очередь, и сейчас метод top() должен его вернуть. Что будем делать? Ничего не возвращать? Вытащим этот элемент из начала очередь и засунем опять в конец?
В данный момент мне не важно, что конкретно произойдет в данном случае. Мне интересно как пишутся эти критерии соритровки. Т.е. просто научиться...
template <class T> struct my_sort: public binary_function<T, T, bool> {
// функция должна быть константной, поскольку так же из константной и вызывается int s(int value) const { int sum = 0; while(value > 0) { sum += value %10; value /= 10; } return sum; }
// вот, собственно, что нам и требовалось: bool operator() (const T& first, const T& second) const { return s(first) > s(second); } };
int main() { const int n = 10; int arr[10] = {121, 311, 37, 114, 555, 436, 2117, 128, 979, 234}; priority_queue< int, vector<int>, my_sort<int> > q; for(int i = 0; i < n; i++) { q.push(arr[i]); }
while (q.size() > 0) { int value = q.top(); q.pop(); cout << value << endl; } return 0; }
Попробуй догадаться, в каком порядке будут выводиться числа из приоритетной очереди?
Цитата
можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как
Спасибо. Числа выведутся по неубыванию суммы цифр, а при совпадении суммы - случайно? Можно ли добавить условие: например при равенстве суммы по неубыванию чисел?
vector< vector<int> > mx(2, vector<int>());
Можно ли теперь этот вектор "поместить" в приорететную очередь? Или может это можно сделать иначе... Вот, что нужно: (Это нужно для реализации Дейкстры с приорететной очередью. С массивами я делал, но так быстрее. Если будет понятнее, могу выложить код простой Дейкстры и указать что нужно заменить.)
Например у меня есть два "типа" данных - один кратчайшее расстояние до вершины, а второй - номер вершины. Эти расстояния должны находиться в очереди и на каждом шаге алгоритма извлекаться минимаьное, но в тоже время нужно как-то хранить информацию до какой вершины это расстояние.
Как это лучше сделать: отдельно вершины, а в очереди расстояния или все вместе можно как-то в очередь поместить?
и все будет работать. Вопрос в том, надо ли оно... Приводи свою реализацию Дейкстры, посмотрим, что можно заменить, и вообще, как ускорить. Только приводи вместе с исходными данными (если они есть, конечно).
#include <fstream> using namespace std; int main () { bool flag=true; const int MAXN=100; int sm[MAXN][MAXN], //матрица смежности b[MAXN]={0}, //множества d[MAXN], //расстояния i,j,p,n,s,f; ifstream in("input.txt"); ofstream out("output.txt"); in>>n>>s>>f; s--; //из какой f--; //в какую for(i=0;i<n;d[i]=-1,b[i]=2,i++); //расстояния до всех -1, все принадлежат к 3 множеству b[s]=0; //начальную вершину в 1 множество d[s]=0; //расстояние до нее 0
/*1 множество - минимальное расстояние найдено 2-расстояние найдено, но не известно минимально ли оно, 3-пути нет*/
for(i=0;i<n;i++) for(j=0;j<n;j++) in>>sm[i][j]; for(i=0;i<n;i++) //нахожу соседей начальной вершины if (sm[s][i]>0) { b[i]=1; d[i]=sm[s][i]; } while (flag) { flag=false; int m=-1; //бесконечность for(i=0;i<n;i++) //нахожу минимум из расстояний от началной вершины до вершин из 2 множества if (b[i]==1 && (d[i]<m || m==-1)) { m=d[i]; p=i; } b[p]=0; //переношу эту вершину в 1 множество for(i=0;i<n;i++) //пробегаюсь по соседям этой вершины if (sm[p][i]!=-1) //если путь есть { if (b[i]==2) b[i]=1; if (b[i]==1) { if (d[i]==-1) d[i]=d[p]+sm[p][i]; else d[i]=min(d[i],d[p]+sm[p][i]); //выбираю минимум из того, что было и что нашел } } for(i=0;i<n;i++) if (b[i]==1)//если есть вершины второго множества продолжаем flag=true; } out<<d[f]; return 0; }
Вход: 3 1 2 0 -1 2 3 0 -1 -1 4 0 выход: 6
-1 означает отсутствие пути.
С такими ограничениями все, конечно, работает. Но вдруг попадется задача с бОльшими да и просто интересно сделать...
Велосипед изобретать может и не нужно, а понять как колеса крутятся хочется.
Почитал эту реализацию, но... не понятно очень много. Непонимание начинается с typedef, а дальше не совсем понятно как обращаются к элементам очереди; по какому полю идет соритровка (я догадываюсь, что должна идит по полю с расстоянием), но какое оно: первое, второе?
если можете, поясните пожалуйста, как поместить в очередь эту pair, и как потом обращаться к элементам...
P.S. Попробую почитать то, что выше, может поможет
Вот алгоритм T.Budd-а, подправленный Sedgewick-ом, и перенесенный мной на описанную задачу (я не стал заморачиваться со вводом матрицы, не думаю, что это будет проблемой):
// карта, содержит мин. дистанцию от каждого узла до всех остальных typedef map<int, unsigned int> nodeInfo; typedef map<int, nodeInfo> graph; // а это свяжет каждый узел с соседями...
// пока очередь не пуста: while(!que.empty()) { // забираем мин. путь из очереди int newNode = que.top().destination; int dist = que.top().distance; que.pop();
// если этот узел ранее не посещался if(minDistance.count(newNode) == 0) { // посетим-ка его... minDistance[newNode] = dist; // и все узлы, доступные из него добавим в очередь nodeInfo::iterator start = theMap[newNode].begin(); nodeInfo::iterator stop = theMap[newNode].end();
for(; start != stop; ++start) { int destNode = (*start).first; unsigned int destDistance = (*start).second; que.push(Destination(destNode, dist + destDistance)); } } } } int main() { graph g;
// отсутствие пути задается числом 100000, поскольку это unsigned int... g[0][0] = 0; g[0][1] = 100000; g[0][2] = 2; g[1][0] = 3; g[1][1] = 0; g[1][2] = 100000; g[2][0] = 100000; g[2][1] = 4; g[2][2] = 0;
nodeInfo dests; dijkstra(g, 0, dests); nodeInfo::iterator it = dests.begin(), stop = dests.end(); for( ; it != stop ; it++ ) { std::cout << "расстояние до " << it->first << " равно " << it->second << '\n'; } return 0; }