BOJ 1916 최소비용 구하기

사용한 알고리즘

다익스트라

알고리즘 설명

각 도시를 Vertex로 하고 각 도시의 버스 비용을 가중치로 하는 그래프를 구성한다.
이후 시작점에서 다익스트라 알고리즘을 적용한다.
도착점의 최소 비용을 출력한다.

풀이

// baekjoon 1916 yechan
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1e9;
const int MAX_N = 1001;
const int MAX_V = 100001;
typedef pair<int, int> P;

int N, V, S, E;
vector<int> dist;
vector<bool> visited;
vector<vector<P> > adj;

int main(){
	scanf("%d", &N);
	scanf("%d", &V);
	dist.resize(N, INF);
	visited.resize(N, false);
	adj.resize(N);

	while (V--) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u-1].push_back(P(v-1,w));
	}

	scanf("%d%d", &S, &E); S--, E--;

	priority_queue<P, vector<P>, greater<P>> PQ;
	dist[S]=0;
	PQ.push(P(0, S));
	while (!PQ.empty()) {
		int curr;
		do {
			curr = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[curr]);
		if (visited[curr]) break;
		visited[curr]=true;
		for (auto &p: adj[curr]) {
			int next=p.first, d=p.second;
			if (dist[next] > dist[curr] + d) {
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}
	printf("%d\n", dist[E]);
	return 0;
}