[알고리즘] 백준 1916번: 최소비용 구하기 (C++)

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

일반적인 다익스트라(우선순위 큐 사용)를 제출하면 시간 초과가 난다.

우선순위 큐에서 현재의 top이 도착하려는 노드(v2)가 되면 이미 최소 비용은 구했기 때문에 다른 노드를 향한 최소 비용을 구할 필요 없이 바로 종료시켜줬다.

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define MAX 1000 + 1
#define INF 987654321
using namespace std;

int N, M;
vector<pair<int, int>> graph[MAX];
int dist[MAX];
int v1, v2;

struct cmp {
	bool operator()(pair<int, int>& a, pair<int, int>& b) {
		return a.second > b.second;
	}
};

void dijkstra(int node) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	dist[node] = 0;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;
		pq.pop();

		// 바로 종료시킨 부분
		if (now == v2) {
			return;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	cin >> v1 >> v2;
	dijkstra(v1);
	cout << dist[v2];

	return 0;
}