leetcode

0 class Graph {

1 typedef tuple<int, int> Edge;

2 vector<vector<Edge>> adj;

3

4 public:

5 Graph(int n, const vector<vector<int>> &edges) : adj(n) {

6 for (const auto &edge : edges)

7 addEdge(edge);

8 }

9

10 void addEdge(const vector<int> edge) { adj[edge[0]].push_back({edge[2], edge[1]}); }

11

12 int shortestPath(int node1, int node2) const {

13 if (node1 == node2) return 0;

14 priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

15 static int seen[101];

16 memset(seen, 0x00, sizeof(seen));

17 for (const Edge edge : adj[node1])

18 pq.push(edge);

19 while (!pq.empty()) {

20 while (!pq.empty() && seen[get<1>(pq.top())])

21 pq.pop();

22 if (pq.empty()) break;

23 const auto [w, n] = pq.top();

24 pq.pop();

25 if (n == node2) return w;

26 seen[n] = true;

27 for (const auto [w2, n2] : adj[n]) {

28 if (!seen[n2]) pq.push({w + w2, n2});

29 }

30 }

31 return -1;

32 }

33 };