BOJ 백준 11779 : 최소비용 구하기 2

시작하면서

　이번 문제는 다익스트라 알고리즘(Dijkstra Algorithm) 과 관련된 문제이다.

BOJ 11779 - 최소비용 구하기 2

​

문제 이해

​ 이 문제는 단순하게 최소 경로를 찾는 문제이다. 그런데 함정이 있다.

• 한 도시에서 다른 도시로 도착하는 경로는 1개만 있지 않고, 여러 개가 존재할 수 있다.

​ 일부로 고치지 않는건지 모르겠지만, 이 조건 때문에 고민을 많이 했다. 결론은 input을 받을 때 가장 짧은 거리만 받으면 된다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>

using namespace std;

struct RouteInformation
{
	int currentNode;
	int weight;
};

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<vector<int>> graph;
	int n, m;

	cin >> n >> m;

	graph.resize(n + 1);
	for (int i = 0; i < n + 1; i++)
	{
		graph[i].resize(n + 1, INT_MAX);
	}

	for (int i = 0; i < m; i++)
	{
		int from, to, weight;
		cin >> from >> to >> weight;

		if (weight >= graph[from][to])
			continue;

		graph[from][to] = weight;
	}

	int start, end;
	cin >> start >> end;

	vector<pair<queue<int>, int>> minimumRouteInformation(n + 1);
	for (int i = 0; i < n + 1; i++)
	{ 
		minimumRouteInformation[i].second = INT_MAX;
	}
	minimumRouteInformation[start].first.push(start);

	queue<RouteInformation> routeInformationQueue;
	RouteInformation routeInformation;	
	routeInformation.currentNode = start;
	routeInformation.weight = 0;
	routeInformationQueue.push(routeInformation);

	while (routeInformationQueue.empty() == false)
	{
		RouteInformation front = routeInformationQueue.front();
		routeInformationQueue.pop();

		int size = graph[front.currentNode].size();
		for (int i = 0; i < size; i++)
		{
			if (i == front.currentNode)
				continue;

			if (graph[front.currentNode][i] == INT_MAX)
				continue;

			int weightSum = front.weight + graph[front.currentNode][i];
			if (weightSum >= minimumRouteInformation[i].second)
			{
				continue;
			}

			minimumRouteInformation[i].first = minimumRouteInformation[front.currentNode].first;
			minimumRouteInformation[i].first.push(i);
			minimumRouteInformation[i].second = weightSum;

			if (i == end)
			{
				continue;
			}

			RouteInformation next = front;
			next.currentNode = i;
			next.weight = weightSum;

			routeInformationQueue.push(next);
		}
	}

	cout << minimumRouteInformation[end].second << "\n" << minimumRouteInformation[end].first.size() << "\n";

	while (minimumRouteInformation[end].first.empty() == false)
	{
		cout << minimumRouteInformation[end].first.front() << " ";
		minimumRouteInformation[end].first.pop();
	}
	
	return 0;
}