单源最短路径

vector<int> dijkstra(int n, int s) {
	vector<vector<pair<int, int>>> edges; // node, dist
	
	vector<int> dist(n, INT_MAX);
	dist[s] = 0;
	
	// dist, node
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, s});
	
	while (!pq.empty()) {
		auto &[d, u] = pq.top();
		pq.pop();
		
		if (dist[u] < d) {
			continue;
		}
		
		for (auto &[v, w] : edges[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + v;
				pq.push({dist[v], v});
			}
		}
	}
	return dist;
}