Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct edge {};
- struct pq_node
- {
- int node;
- ll distance;
- pq_node() {}
- pq_node(int _node, ll _distance)
- {
- node = _node, distance = _distance;
- }
- };
- struct pq_node_comp
- {
- bool operator()(pq_node& l, pq_node& r)
- {
- return l.distance < r.distance;
- }
- };
- std::vector<ll> Dijkstra(int src, std::vector<std::vector<edge>>& edges)
- {
- std::vector<ll> dist(size(), ll_inf);
- dist[src] = 0;
- std::priority_queue<pq_node, std::vector<pq_node>, pq_node_comp> PQ;
- PQ.push(pq_node(src, 0));
- while (!PQ.empty())
- {
- pq_node from = PQ.top();
- PQ.pop();
- for (edge& e : edges[from.node])
- if (from.distance + e.weight < dist[e.to])
- PQ.push(pq_node(e.to, dist[e.to] = from.distance + e.weight));
- }
- return dist;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement