[C++] 백준 11779번: 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

중요풀이

가장 유명한 알고리즘 중 하나인 다익스트라 알고리즘을 기반으로 풀이되는 문제입니다.

큐를 활용하여 풀이를 진행해 주어야 합니다.

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

using namespace std;

vector<pair<int, int>> city[1001];
vector<int>v[1001];
int INF = 100000001;// 전체길이가 1억까지는 가능하기 때문에 그것보다 커야함
int d[1001];
int N, M;
int ans[1001];//경로 추적
vector<int> st;

void Dijkstra(int s, int e) {
	queue<pair<int, int>>q; // {index, distance}
	//인덱스 순으로 정렬해서 들어오기 때문에 큐를 사용
	for (int i = 1; i <= N; i++)
		d[i] = INF;
	q.push({ s, 0 });
	v[s].push_back(s);
	while (!q.empty()) {
		int cur = q.front().first;
		int distance = q.front().second;//그냥 큐로 구현해준다.
		q.pop();
		if (d[cur] < distance)continue;
		for (int i = 0; i < city[cur].size(); i++) {
			int next = city[cur][i].first;
			int nextDistance = distance + city[cur][i].second;
			if (nextDistance < d[next]) {
				//이렇게하하면 시간초과
				//v[next].clear();
				//for (int i = 0; i < v[cur].size(); i++)
				//	v[next].push_back(v[cur][i]);
				//v[next].push_back(next);
				ans[next] = cur;
				d[next] = nextDistance;
				q.push({ next,nextDistance });
			}
		}
	}
	int temp = e;
	st.push_back(e);
	while (temp != s) {//역추적
		temp = ans[temp];
		st.push_back(temp);
	}

	cout << d[e] << '\n';
	cout << st.size() << '\n';

	for (int i = st.size() - 1; i >= 0; i--)
		cout << st[i] << ' ';
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int a, b, d, s, e;
	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> d;
		city[a].push_back({ b,d });
		//city[b].push_back({ a,d });
	}

	cin >> s >> e;

	Dijkstra(s, e);

	return 0;
}