Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //BFS и алгоритм Дейкстры. Теория. Задача B.
- #include <bits/stdc++.h>
- using namespace std;
- int n, m, start, finish;
- vector < vector < pair < int , int > > > g;
- vector < int > dist;
- vector < int > from;
- void Dijkstra() {
- dist.resize(n, 1e9 + 7);
- from.resize(n);
- from[start] = -1;
- dist[start] = 0;
- set < pair < int , int > > s;
- s.insert({0, start});
- while (!s.empty()) {
- auto c = *s.begin();
- s.erase(s.begin());
- int v = c.second;
- for (auto e : g[v]) {
- int u = e.first, d = e.second;
- if (dist[u] > dist[v] + d) {
- s.erase({dist[u], u});
- dist[u] = dist[v] + d;
- from[u] = v;
- s.insert({dist[u], u});
- }
- }
- }
- }
- void print_way() {
- if (dist[finish] == 1e9 + 7) {
- cout << -1;
- return;
- }
- cout << dist[finish] << endl;
- vector < int > vs;
- int v = finish;
- while (from[v] != -1) {
- vs.push_back(v);
- v = from[v];
- }
- vs.push_back(start);
- reverse(vs.begin(), vs.end());
- cout << vs.size() << endl;
- for (auto u : vs) cout << u + 1 << " " ;
- }
- int main() {
- cin >> n >> m;
- cin >> start >> finish;
- start--; finish--;
- g.resize(n);
- for (int i = 0; i < m; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- a--; b--;
- g[a].push_back({b, c});
- g[b].push_back({a, c});
- }
- Dijkstra();
- print_way();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement