[C++] 백준 1916 : 최소비용 구하기

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

1916번: 최소비용 구하기

백준 1916번 최소비용 구하기를 풀었다.

 

최대 N이 1000이므로 플로이드 와샬로는 풀 수 없다.

그래서 인접리스트를 이용한 다익스트라 알고리즘으로 풀었다.

같은 시작 노드 u와 같은 도착 노드 v에 대해 다른 비용의 입력이 들어 올 수 있다.

예를 들어 2 3 2와 2 3 10이 입력으로 들어 올 수 있다. 그러면 비용이 더 큰 버스에 대해선 연산을 건너 뛰어야 한다.

그래서 다익스트라 함수에서 dist[cur] < cost 일 때 현재 노드에 대한 연산을 실행하지 않았다.

 

아래는 전체 코드입니다.

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define INF 1000000000

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

vector<pair<int, int>> adj[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
int dist[1001];

void dijkstra() {
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
		if (dist[cur] < cost) // Same path, different cost
			continue;
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first;
			int next_cost = adj[cur][i].second + cost;
			if (dist[next] > next_cost) {
				dist[next] = next_cost;
				pq.push({ next,next_cost });
			}
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;

	int from, to, cost;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back({ to,cost });
	}

	for (int i = 0; i <= 1000; i++)
		dist[i] = INF;

	int start, destination;
	cin >> start >> destination;

	dist[start] = 0;
	pq.push({ start,dist[start] });
	dijkstra();

	cout << dist[destination];

	return 0;
}