백준(BOJ) 11779 최소비용 구하기 2 **

본인은 다익스트라 알고리즘을 이용해서 풀었다.

1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다.
2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다.

가장 기본적인 방식으로 푼것 같다.

** : 가장 기본적인 다익스트라 방식이고, 최소비용 뿐 아니라 경로를 저장하는 부분이 추가되었다.

#include 
#include 
#include 
#include 
#include 
#define MAX 100000001
#pragma warning(disable:4996)
using namespace std;

int city_n,bus_n,bus[1005][1005],city[2][1005],a,b,c;
vector v[1005],current;

int getMin(void)
{
	int mi=-1,val=MAX;
	for (int i = 1; i <= city_n; i++)
	{
		if (city[1][i] == 0 && city[0][i] < val)
		{
			val = city[0][i];
			mi = i;
		}
	}
	if (mi != -1)
		city[1][mi] = 1;
	return mi;
}
// 1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다.
void update(int str)
{
	for (int i = 1; i <= city_n; i++)
	{
		if (bus[str][i] + city[0][str] < city[0][i])
		{
			city[0][i] = bus[str][i] + city[0][str];
			v[i] = current;
			v[i].push_back(i);
		}
	}
}
// 2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다.
void djk(void)
{
	int next=a;
	while (next != -1)
	{
		update(next);
		next = getMin();
		current = v[next];
	}
}
// 다익스트라 알고리즘
int main()
{
	fill_n(&city[0][0], 1005 * 2, 0);
	fill_n(&city[0][0], 1005 , MAX);
	fill_n(&bus[0][0], 1005 * 1005, MAX);

	scanf("%d %d", &city_n, &bus_n);
	for (int i = 1; i <= bus_n; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		if (c < bus[a][b])
			bus[a][b] = c;
	}

	scanf("%d %d", &a, &b);
	current.push_back(a);
	city[0][a] = 0;
	city[1][a] = 1;
	c = 0;

	djk();

	printf("%d\n%d\n", city[0][b],v[b].size());
	for (int i = 0; i < v[b].size(); i++)
		printf("%d ", v[b][i]);
	return 0;
}