개요

백준 1916번: 최소비용 구하기

• 입력
  첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

  그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

• 출력
  첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

접근 방식

1. 전형적인 다익스트라 알고리즘을 활용한 문제로
   [백준 1753번: 최단경로] 문제와 동일하다.
2. • 이차원 벡터를 이용해 시작노드, 끝노드, 비용을 저장한다.
   • 배열을 이용해 최단 거리 갱신,
   • 배열을 이용해 방문 여부 체크
   • 우선순위 큐를 이용해 현재 최단거리가 제일 짧은 노드에서
     주위 노드로 이동비용 계산하며 최단거리 갱신해주기

전체코드

#include<iostream>
#include<vector>
#include<queue>


using namespace std;
//index는 시작점, pair.first는 도착점, pair.second는 비용
vector<vector<pair<int, int>>> adj;
//방문여부
bool visited[1001];
//시작도시로부터의 최단 비용
int minCost[1001];
//비용최대값 10만, 도시 최대갯수 1000개라서 나올수 있는 최대거리는 9990만 이다
int N, M,startCity,endCity,MaxInt=100'000'000;
//정렬기준인 fisrt값은 해당 노드까지의 거리, second값은 해당 노드
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;


void Solution() {
	while (!pq.empty()) {
		int curNode = pq.top().second;
		pq.pop();
		while (!pq.empty() && visited[curNode]) {
			curNode = pq.top().second;
			pq.pop();
		}

		//pq가 비어있고 curNode가 방문한 노드라면 탈출
		if (visited[curNode]) break;

		//방문처리해주기.
		visited[curNode] = true;

		//curNode주변 노드들의 최단거리값을 비교,갱신해주며 갱신되었다면 pq에 넣어줌
		for (pair<int, int>& p : adj[curNode]) {
			int nextNode = p.first, nextCost = p.second;
			if (minCost[nextNode] > minCost[curNode] + nextCost) {
				minCost[nextNode] = minCost[curNode] + nextCost;
				pq.push({ minCost[nextNode],nextNode });
			}
		}
	}
	//목적지까지 가는 거리 출력
	cout << minCost[endCity];
}

void Input() {
	int tmpStart, tmpEnd, cost;
	cin >> N >> M;
	adj.resize(N);
	for (int i = 0; i < M; i++) {
		cin >> tmpStart >> tmpEnd >> cost;
		adj[tmpStart-1].push_back({ tmpEnd - 1, cost });
	}
	cin >> startCity >> endCity;
	//index는 0부터 시작하므로 1빼주기
	startCity--;
	endCity--;
	//방문 여부 다 false로 초기화
	fill(visited, visited + 1001, false);
	//최단 거리 전부 제일 큰값으로 초기화
	fill(minCost, minCost + 1001, MaxInt);
	//시작노드는 최단거리 0으로 
	minCost[startCity] = 0;
	//시작 노드 pq에 넣어주기
	pq.push(make_pair(minCost[startCity],startCity));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

문풀후생

각 비용의 최대값이 10만이고, 도시가 1000개이므로
최대 거리는 999 * 10만으로 9990만이다.
maxInt는 넉넉하게 1억으로 줬다.