백준/1916/다익스트라/최소비용 구하기

백준/1916/다익스트라/최소비용 구하기

문제 해석

A도시에서 B도시로 가는(방향 그래프) 최소 비용을 구하라
(이 때 A에서 B는 갈 수 있는 도시만을 제안한다)

문제 풀이

1. 각 출발 도시 인덱스에 도착 도시 인덱스와 가는 비용 저장
2. 출발 도시 인덱스와 비용을 묶어서 탐색해보기
3. 이 때 큐에 저장해놓은 비용과 현재 저장된 비용이 다를 경우 해당 경로는 최소 비용이 아니게 되므로 제외
4. 해당 경로에서 갈 수 있는 도시와 현재 갈 수 있는 비용을 비교하여 작은 값을 비용에 저장
5. 결과 값 출력

1. 각 출발 도시 인덱스에 도착 도시 인덱스와 가는 비용 저장

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

※ 각 도시의 최소 비용을 구하기 위해 큰 값을 넣어둡니다.

for (int i = 0;i < M;i++)
{	
	int _st, _en, _cost = 0;
	cin >> _st >> _en >> _cost;
	city_cost[_st].push_back({ _en,_cost });
}

2. 출발 도시 인덱스와 비용을 묶어서 탐색해보기

int city_st, city_en = 0;
cin >> city_st >> city_en;

q.push({ city_st,0 });
cost[city_st] = 0;

while (!q.empty())
{
	auto cur = q.front(); q.pop();
	if (cur.second != cost[cur.first])continue;
	for (auto nxt : city_cost[cur.first])
	{
		if (cost[nxt.first] > cur.second + nxt.second)
		{
			cost[nxt.first] = cur.second + nxt.second;
			q.push({ nxt.first,cost[nxt.first] });
		}
	}
}

3. 이 때 큐에 저장해놓은 비용과 현재 저장된 비용이 다를 경우 해당 경로는 최소 비용이 아니게 되므로 제외

auto cur = q.front(); q.pop();
if (cur.second != cost[cur.first])continue;

4. 해당 경로에서 갈 수 있는 도시와 현재 갈 수 있는 비용을 비교하여 작은 값을 비용에 저장

for (auto nxt : city_cost[cur.first])
{
	if (cost[nxt.first] > cur.second + nxt.second)
	{
		cost[nxt.first] = cur.second + nxt.second;
		q.push({ nxt.first,cost[nxt.first] });
	}
}

5. 결과 값 출력

cout << cost[city_en];

풀이

첫번째 풀이

#include<iostream>
#include<queue>
using namespace std;

int cost[1001];
// 현재 지점, 현재 지점까지 가는 값
queue<pair<int, int>>q;
// 메모리 초과시 2차원 배열로 시도
vector<pair<int, int>>city_cost[1001];

int INF = 0x3f3f3f3f;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// N은 도시 수, M은 경로의 수
	int N, M = 0;
	cin >> N >> M;

	city_cost->resize(N + 1);

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

	for (int i = 0;i < M;i++)
	{	
		int _st, _en, _cost = 0;
		cin >> _st >> _en >> _cost;
		city_cost[_st].push_back({ _en,_cost });
	}

	int city_st, city_en = 0;
	cin >> city_st >> city_en;

	q.push({ city_st,0 });
	cost[city_st] = 0;

	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		if (cur.second != cost[cur.first])continue;
		for (auto nxt : city_cost[cur.first])
		{
			if (cost[nxt.first] > cur.second + nxt.second)
			{
				cost[nxt.first] = cur.second + nxt.second;
				q.push({ nxt.first,cost[nxt.first] });
			}
		}
	}

	cout << cost[city_en];

	return 0;
}