Алгоритм Дейкстры

Мне нужно восстановить минимальный путь в графе, от вершины s до f, используя алгоритм Дейкстры. Моя идея - запоминать вершину-родителя для каждой вершины, относительно минимального расстояния для которой мы уверены. Решение не проходит половину тестов, не могли вы помочь мне, указав на ошибку?
#include #include #include #include #include
using namespace std;
vector > graph; vector dist; vector used; vector parrent;
void djkstera(long long u, long long &n, long long &v){ set > que; que.insert({0, u}); dist[u] = 0; long long parr = u;
while(!que.empty()){
while(!que.empty() && used[(*que.begin()).second]){ que.erase(que.begin()); }
if(que.empty()) break;
u = (*que.begin()).second; used[u] = true; parrent[u] = parr; parr = u; que.erase(que.begin());
for(long long i = 0; i < n; ++i){ if(graph[u][i] != -1 and u!=i){ dist[i] = min(dist[i], dist[u] + graph[u][i]); que.insert({dist[i], i}); } } } }
int main() { long long n,s,f; cin >> n >> s >> f; // s - start, f - finish s--; f--; graph.assign(n, vector(n)); used.assign(n, false); dist.assign(n, INT64_MAX); parrent.resize(n);
//Граф задаётся матрицой смежности for(long long i = 0; i < n; ++i){ for(long long j = 0; j < n; ++j){ cin >> graph[i][j]; } } djkstera(s, n, f);
//Пути не существует if(dist[f] == INT64_MAX){ cout << "No solution"; return 0; }
vector res; for(long long i = f; i != s; i = parrent[i]){ res.push_back(i + 1); } res.push_back(s + 1); reverse(res.begin(), res.end());
copy(res.begin(), res.end(), ostream_iterator(cout, " "));
return 0; }

Ответ

Всё, сам разобрался. Родителя следует определять после удачной релаксации(если значение в массиве dist было изменено). Получается вот так:
for(long long i = 0; i < n; ++i){ if(graph[u][i] != -1 and u!=i){ if(dist[u] + graph[u][i] < dist[i]){ parrent[i] = u; dist[i] = dist[u] + graph[u][i]; } que.insert({dist[i], i}); } }