1. Пользуйтесь тегами кода. - [code] ... [/code] 2. Точно указывайте язык, название и версию компилятора (интерпретатора). 3. Название темы должно быть информативным. В описании темы указываем язык!!!
А можно ли в priority_queue (ну и в ее подобных) в критерие сортировки указать (если равно чему-то то не соритровать)? Например, мне нужно сформировать heap, но чтобы первый элемент не был равен X.
P.S. И вот еще такой вопрос созрел: можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как, и как потом с этим работать?
Вот алгоритм 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; }