Условия сортировки в STL, C++ Опции

[first_day]

А можно ли в priority_queue (ну и в ее подобных) в критерие сортировки указать (если равно чему-то то не соритровать)? Например, мне нужно сформировать heap, но чтобы первый элемент не был равен X.

P.S. И вот еще такой вопрос созрел: можно ли из вектора сделать что-то вроде двумерного массива (т.е. не 1 строка, а 2 например)? если да, то как, и как потом с этим работать?

Сообщение отредактировано: first_day - 3.05.2008 15:06

[volvo]

Вот алгоритм T.Budd-а, подправленный Sedgewick-ом, и перенесенный мной на описанную задачу (я не стал заморачиваться со вводом матрицы, не думаю, что это будет проблемой):

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

class Destination {
    public:
        int destination;        // куда путь держим - номер узла
        unsigned int distance;  // расстояние до этого узла

        // конструктор класса Destination
        Destination(int dt, unsigned int ds): destination(dt), distance(ds) {
        }

        bool operator < (const Destination& right) const {
            return distance > right.distance;
        }  // изменяем порядок приоритетной очереди на "первый - меньший"
};

// карта, содержит мин. дистанцию от каждого узла до всех остальных
typedef map<int, unsigned int> nodeInfo;
typedef map<int, nodeInfo> graph; // а это свяжет каждый узел с соседями...

void dijkstra(graph& theMap, int start_from, nodeInfo& minDistance)
{
    priority_queue <Destination> que;
    que.push(Destination(start_from, 0));

    // пока очередь не пуста:
    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;
}