형진_유니콘

1. A, B, C(버스 비용) 이라고 했을 때 최소 비용 구하기.

2. 마지막 줄에는 출발 노드가 정해짐.

3. 보통 이와 비슷한 도시와 도시를 이동하면서 출발과 도착노드가 케이스마다 다르므로 모든 정점의 거리를 구해야 함.

4. 이와 관련해서 다익스트라 알고리즘을 사용하여 최단 경로를 탐색해보기로 했음.

먼저 다익스트라 알고리즘에서 dist 벡터를 선언해주는데 보통 9억 이상의 수를 이용하여 INF를 나타낸다.

그래서 나는 #define INF 999999999 로 설정하여 dist 벡터를 채워주기로 하였다.

int N, M;

cin >> N >> M;
vector<vector<pair<int, int>>> city(N+1);
vector<int> dist(N + 1, INF);

N은 노드 개수, M은 엣지 개수라고 생각하자.

city는 우리가 계산하기 쉽게 N+1까지 설정했다. 여기서 나는 노드의 비용과 자식 노드를 넣고싶어서 pair를 사용하여 두개의 데이터를 넣을 수 있게하였다.

위에서 말했듯 dist의 값을INF로 채워주도록 했다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>>  heap;

나는 MST나 다익스트라와 같은 알고리즘에서 최소 힙을 사용해서 푸는것이 편하기 때문에 우선순위큐를 오름차순으로 정렬하여 최소 힙을 만들어주었다.

그래서 데이터들을 각각 받아주고 아래와 같이 다익스트라를 실행시켜준다.

heap.push({ 0,st });

heap은 앞에 데이터를 가지고 정렬하기 때문에 비용을 first에 넣어주고 시작점을 먼저 힙에 넣어준다.

while (!heap.empty())
{
	auto node = heap.top();
	heap.pop();
	if (dist[node.second] < node.first) continue;

	for (auto a : city[node.second])
	{
		if (dist[a.second] > node.first + a.first)
		{
			dist[a.second] = node.first + a.first;
			heap.push({ dist[a.second],a.second });
		}
	}
}

1. 진행은 이와 같다. 힙이 다 없어질때까지 while문을 반복하면된다.

2. node에 힙에서 먼저 넣어준 노드를 가져오고 pop을 해준다.

3. 이미 저장되어있는 노드 까지의 비용보다 지금 까지의 노드 비용이 더크다면 그냥 무시한다.

4. 아니면 for문을 시작한다. 아까 힙에서 꺼내온 노드와 연결된 노드들을 모두 가져와서 그동안 지나왔던 비용과 연결된 노드의 비용을 더한 값이 기존에 있던 비용보다 낮다면 비용을 고쳐주고 그 노드를 heap에다가 push 한다.

5. 이렇게 모두 더해주게 되면 각 노드의 비용은 최소 값으로 들어가 있게된다.

전체 코드 내용은 아래와 같다.

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

using namespace std;

#define INF 999999999

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

	
	int N, M;
	
	cin >> N >> M;
	vector<vector<pair<int, int>>> city(N+1);
	vector<int> dist(N + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>>  heap;
	
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		city[a].push_back({ c,b });
	}

	int st, ed;
	cin >> st >> ed;
	heap.push({ 0,st });

	while (!heap.empty())
	{
		auto node = heap.top();
		heap.pop();
		if (dist[node.second] < node.first) continue;

		for (auto a : city[node.second])
		{
			if (dist[a.second] > node.first + a.first)
			{
				dist[a.second] = node.first + a.first;
				heap.push({ dist[a.second],a.second });
			}
		}

	}
	cout << dist[ed];

	
	return 0;
}