백준 11779, 최소비용 구하기 2

문제

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

풀이

골3 문제여서 기대했는데 저번에 풀었던 다익스트라랑 별반 차이가 없다. 저번이랑 달라진 점은 최종 경로를 기억하는 것이 문제로 추가 되었다는 점. 근데 그건 cost를 갱신 할때마다 해당 노드만 기억하면 linked list처럼 back하면서 찾을 수 있어서 큰 문제가 되지 않는다.

그래서 그냥 다익스트라 문제였다.

따로 찾아보니까 다익스트라도 우선순위로 구현하는 것이 있다고 한다.

간단한 구현 -> O(E + V^2)
우선순위 큐를 이용한 구현 -> O((E + V) log V)

관련 구현문제도 한번 풀어보자.

실수

• 푸는데 시간이 오래걸림 (40분)
• next 초기화 안해서 값이 잘못 출력됨. (디버깅 못했으면 더 오래걸리지 않았을까 생각)

코드

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int n, m;
int a, b;
vector<vector<pair<int, int>>> graph(1001, vector<pair<int, int>>(0, make_pair(300000000, 0)));
vector<int> cost(1001, 300000000);
vector<int> visit(1001, 0);
vector<int> prev_node(1001, 0);

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++) {

		int temp1, temp2, temp3;

		scanf(" %d %d %d", &temp1, &temp2, &temp3);

		graph[temp1].push_back(make_pair(temp2, temp3));

	}

	scanf(" %d %d", &a, &b);

	int next = a;
	cost[a] = 0;

	for (int i = 0; i < n; i++) {

		next = 0; // 초기화 (항상 다른 값으로 바뀜이 보장됨, 문제 조건)

		for (int j = 1; j <= n; j++) {

			if (cost[next] > cost[j] && visit[j] == 0) {

				next = j; // 항상존재

			}

		}

		visit[next] = 1;

		for (int j = 0; j < graph[next].size(); j++) { 

			if (cost[graph[next][j].first] > cost[next] + graph[next][j].second) {

				cost[graph[next][j].first] = cost[next] + graph[next][j].second;
				prev_node[graph[next][j].first] = next;

			}

		}

	}

	next = prev_node[b];
	vector<int> result;

	result.push_back(b);

	while (next != 0) {

		result.push_back(next);
		next = prev_node[next];

	}

	printf("%d\n", cost[b]);
	printf("%d\n", result.size());
	
	for (int i = 1; i <= result.size(); i++) {

		printf("%d ", result[result.size() - i]);

	}

	return 0;

}