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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
int N = 0;
int M = 0;
 
int iFirst = 0;
int iSecond = 0;
int iLong = 0;
 
int route[1001] = {};
int visit[1001] = {};
std::vector<std::pair<int,int>> vec[1001] = {};
std::vector<int> vecAns = {};
 
void Dijkstra(int iStart)
{
	std::priority_queue<std::pair<int, int>,
		std::vector<std::pair<int, int>>,
		std::greater<std::pair<int, int>>> pri_que = {};
	pri_que.push({ 0, iStart });
	visit[iStart] = 0;
 
	while (!pri_que.empty())
	{
		int iCost = pri_que.top().first;
		int iNow = pri_que.top().second;
		pri_que.pop();
 
		if (iCost > visit[iNow])
			continue;
 
		for (int i = 0; i < vec[iNow].size(); ++i)
		{
			int iNextCost = vec[iNow][i].second;
			int iNext = vec[iNow][i].first;
 
			if (visit[iNext] > visit[iNow] + iNextCost)
			{
				route[iNext] = iNow;
				visit[iNext] = visit[iNow] + iNextCost;
				pri_que.push({ visit[iNext], iNext });
			}
		}
	}
}
 
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	std::cin >> N >> M;
 
	for (int i = 0; i < M; ++i)
	{	
		std::cin >> iFirst >> iSecond >> iLong;
 
		vec[iFirst].push_back({iSecond, iLong});
	}
 
	for (int i = 1; i <= N; ++i)
	{
		visit[i] = 2147483647;
	}
 
	std::cin >> iFirst >> iSecond;
 
	Dijkstra(iFirst);
 
	std::cout << visit[iSecond] << "\n";
 
	int iEnd = iSecond;
 
	while (iEnd)
	{
		vecAns.push_back(iEnd);
		iEnd = route[iEnd];
	}
 
	std::cout << vecAns.size() << "\n";
 
	for (int i = vecAns.size() - 1; i >= 0; --i)
	{
		std::cout << vecAns[i] << " ";
	}
 
	std::cout << "\n";
 
	return 0;
}

다익스트라자 문제입니다.

기존 거리구하는 건 다익스트라자로 풀면서 경로를 구해야했습니다.

경로는 변경될 때마다 이전 경로를 입력해서 마지막 경로를 찾아낼 수 있도록 연결해줬습니다.

함수 내에서 Cost가 넘어갈 때는 continue를 해주지 않는다면 무조건 시간초과가 나왔습니다.

이 점은 이전에 모두 넣어둔 것들을 빼내야 하기 때문에 해야했습니다.