Dijkstra

Dijkstra.cpp

typedef pair<int, int> point;
const int INF = 987654321;
//정점의 개수
int V;
//그래프의 인접리스트 (연결된 정점 번호, 간선 가중치)
vector<point> adj;
vector<int> dijkstra(const int& src) {
	vector<int> dist(V, INF);
	dist[src] = 0;
	priority_queue<point> pq;
	pq.push(make_pair(0, src));
  
	while (not pq.empty()) {
		const int cost = -pq.top().first;
		const int here = pq.second().second;
		pq.pop();
		if (dist[here] < cost) continue;
		
		for (const point& next : adj[here]) {
			const int nextCost = cost + next.second;
			const int there = next.first;
			if (nextCost < dist[there]) {
				dist[there] = nextCost;
				pq.push(make_pair(-nextCost, there));
			}
		}
	}
	return dist;
}