백준1916 최소비용 구하기 - C++

A -> B 로 가는 최소비용을 구하면 된다.

A -> B 로 갈 수 있는 경우만 입력으로 주어진다는 조건이 있으므로

최소 비용 구하는 것만 신경쓰면 된다.

 

여기서 버스 비용은 0 이상이므로 버스를 이용할수록 손해이므로

버스는 최대 N-1 번 이용할 것이고,

한 번 타는데 최대 비용은 10^5 이고 N 은 10^3 이므로 

최대 나올 수 있는 비용은 10^8 이므로 int 로 처리한다.

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N, M, s, e, c;
int start_city, end_city;
vector<pair<int, int>> edge[1001];//[도시번호] pair(비용,다음도시)


int dijkstra(int start_city, int end_city) {

	int dest[1001];
	memset(dest, 0x7f, sizeof(dest));
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair( 0,start_city));
	dest[start_city] = 0;

	while (!pq.empty()) {
		int cur_city = pq.top().second;
		int cur_cost = -pq.top().first; pq.pop();
		if (dest[cur_city] != cur_cost) continue;
		
		for (int i = 0; i < edge[cur_city].size(); i++) {
			int next_city = edge[cur_city][i].first;
			int next_cost = edge[cur_city][i].second;

			if (cur_cost + next_cost >= dest[next_city]) continue;
			dest[next_city] = cur_cost + next_cost;
			pq.push(make_pair(-dest[next_city], next_city));

		}
	}
	return dest[end_city];
}

int main() {
	scanf("%d", &N);
	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &s, &e, &c);
		edge[s].push_back(make_pair(e, c));
	}

	scanf("%d %d", &start_city, &end_city);
	printf("%d\n", dijkstra(start_city, end_city));
	
}