Задача e-olimp.com №4856. Ссылка на засчитанное решение.
Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.
Входные данные
Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].
Выходные данные
Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <vector> #include <set> #include <utility> using namespace std; #define INF 1000000000000 #define MAX 100000 vector <pair <int, long long> > G[MAX]; vector <int> path; vector <int> ans; set <pair <long long, int> > q; long long length[MAX]; int parent[MAX]; int main() { ios::sync_with_stdio(false); int n, m, a, b; cin >> n >> m >> a >> b; a--, b--; // начнём отсчёт с 0, для удобства for (int i=0; i<m; i++) { int from, to, len; cin >> from >> to >> len; from--, to--; G[to].push_back(make_pair(from, len)); G[from].push_back(make_pair (to, len)); } for (int i=0; i<n; i++) length[i]=INF; length[a]=0; q.insert (make_pair (length[a], a)); while (!q.empty()) { // будем выполнять, пока наша очередь не пуста int v = q.begin()->second; q.erase (q.begin()); for (int i=0; i<G[v].size(); i++) { int to=G[v][i].first, len=G[v][i].second; if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них length[to]=length[v]+len; // ставим новую длину parent[to]=v; // и записываем предка q.insert (make_pair (length[to], to)); } } } if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли cout << "-1"; return 0; } cout << length[b] << endl; int c=b; while (c!=a) { ans.push_back(c+1); // так как начинали с 1, то увеличиваем c=parent[c]; } ans.push_back(a+1); cout << ans[ans.size()-1]; for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it]; cout << endl; return 0; } |
Для решения использовался алгоритм Дейкстры, подробнее в комментариях к коду.
Зачтено.
Хорошо бы дать ссылку на описание того варианта алгоритма Дейкстры, который Вы реализовали.