В этой реализации алгоритма Дейкстры граф с весовыми ребрами хранится в виде vector < vector < pair<int,int> > > g.
Допустим нужно написать программу, в которой потребуется пару раз применить эту реализацию алгоритма Дейкстры, но кроме этого в ней потребуется (несколько раз) по паре вершин v и to найти вес ребра (v,to). Я пытаюсь понять какой тут правильный подход. Просто искать в векторе g[v] элемент i, в котором g[v][i].first==to (тогда g[v][i].second будет искомым) или завести map, в котором хранить все расстояния? Как в таком случае правильно организовать поиск веса ребра по его вершинам?
Ну а что мешает хранить
map<pair<int, int>, int>, где ключ — это пара(v, to), а значение — это вес ребра?Не то, что бы что-то мешает, но смущает, что при таком подходе граф хранится в памяти "два раза" (
vector < vector < pair<int,int> > >иmap<pair<int, int>, int>). Поэтому и интересуюсь нет ли подхода лучше.Отсорти список смежности для каждой вершины и ищи lower_bound'ом
Можно ещё хранить
vector<map<int,int>> g, гдеg[v]—mapс ключамиtoи значениями, равными весу соответствующего ребра (подойдет какmap, так иunordered_map).Во! То, что нужно. И реализация Дейкстры практически не меняется и веса смотреть удобно.
Но добавляется лишний логарифм в Дейкстре.
Как сказать, не очень-то добавляется. Асимптотически наибольшее слагаемое
каким было, таким и остаётся, т.к. появление 
.
map-а не влияет ни на доступ к пирамиде илиset-у с оценками расстояний, ни на перебор всех списков смежности (суммарно, амортизационно). Увеличиваются лишь некоторые из изначально меньших слагаемых — например, формирование списков, которое раньше было (суммарно, амортизационно) O(M) (асимптиотически меньшим чем асимптотика всего алгоритма), становится асимтотически таким жеА что касается неасимптотических моментов — весьма вероятно, что ранее рекомендованный вариант "хранить
vector<vector<pair<len,to>>>, но отсортировать каждый отдельный список и искатьlower_bound-ом" лучше. Но ТОЛЬКО если длИны рёбер не надо многократно менять на лету.