Dijkstra Best Practice

cpp nlogn

#include <priority_queue>
#include <vector>
 
using namespace std;
using ll = unsigned long long;
 
struct node {
	ll dest;
	ll dist;
};
vector<vector<node>> arr;
struct cmp {
	bool operator () (node a, node b) {
		return a.dist > b.dist;
	}
};
 
// s -> e로 가는 최소 경로 길이 반환 ( 불가능한 경우 -1 )
ll dijkstra(ll s, ll e) {
	priority_queue<node, vector<node>, cmp> pq;
	vector<ll> cost = vector<ll>(v + 1);
	for (int i = 1; i <= v; i++) {
		cost[i] = MaxVal;
	}
	cost[s] = 0;
	pq.push({ s, 0 });
	while (!pq.empty()) {
		node cur = pq.top(); pq.pop();
		if (cur.dest == e) {
			return cur.dist;
        }        
		for (auto it : arr[cur.dest]) {
			if (cost[it.dest] <= it.dist + cur.dist) continue;
			cost[it.dest] = it.dist + cur.dist;
			pq.push({ it.dest, it.dist + cur.dist });
		}
	}	
	return -1;
}