about summary refs log tree commit diff
path: root/usth/MATH2.3/2/dijkstra.cc
blob: e8a79314b5e4fd1502ec26e23cbc34931a42149a (plain) (blame)
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
#include <iostream>
#include <deque>
#include <queue>
#include <unordered_map>
#include <vector>

#define ENCODE(w, c, p) (((w) << 20) + ((c) << 10) + (p))
#define WEIGHT(x) ((x) >> 20)
#define CUR(x) ((x) >> 10 & 1023)
#define PREV(x) ((x) & 1023)

using namespace std;

int
main ()
{
  size_t n, a, b, w, s, e;
  unordered_map<size_t, unordered_map<size_t, size_t>> edges;

  cin >> n >> s >> e;
  for (size_t i = 0; i < n; ++i)
    {
      cin >> a >> b >> w;
      edges[a][b] = edges[b][a] = w;
    }

  unordered_map<size_t, size_t> prev;
  priority_queue<size_t, vector<size_t>, greater<size_t>> pq;
  pq.push (ENCODE (0, s, s));

  while (!pq.empty ())
    {
      size_t p = pq.top ();
      a = PREV (p);
      b = CUR (p);
      w = WEIGHT (p);
      if (!prev[b])
        prev[b] = a;
      if (b == e)
        break;
      pq.pop ();

      for (auto const& [i, v] : edges[b])
        if (!prev[i])
          pq.push (ENCODE (w + v, i, b));
    }

  deque<size_t> d;
  for (; e != s; e = prev[e])
    d.push_front (e);
  d.push_front (e);
  for (auto const& i : d)
    cout << i << " ";
  cout << "(length of " << w << ")" << endl;
}