[백준/c++] - 1916 최소비용 구하기

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

1916번: 최소비용 구하기

 

 

 

 

 

 

 

 

 다익스트라 연습겸 풀었던 문제인데 개인적으로 꼭 기억해야할 부분이 있어서 글을 써본다. 문제 자체는 특별할 것 없는 다익스트라 구현 문제이다.

 

 

 

 

 

 

 

 문제 풀이 자체에는 문제가 없었는데 계속해서 메모리 초과가 났다. 일단 코드를 보자.

 

 

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <stack>

using namespace std;

// 다익스트라

struct Vertex {
	int vertex;
	int cost;

	bool operator<(const Vertex v) const {
		return this->cost > v.cost;
	}
};


vector<vector<Vertex>> adjacant;
priority_queue<Vertex> dijikstraQueue;
vector<int> best;

int N, E;
int S, D;



void input() {
	cin >> N >> E;

	adjacant.resize(N + 1);
	best.resize(N + 1);
	fill(best.begin(), best.end(), INT_MAX);

	for (int i = 0; i < E; i++) {
		int start, dest, cost = 0;

		cin >> start >> dest >> cost;

		adjacant[start].push_back(Vertex{ dest, cost }); // 인접 배열 방식 저장
	}

	cin >> S >> D;
}

void dijikstra() {
	
	// 출발지 초기화
	Vertex startPos{ S, 0 }; // 출발지 자신까지의 거리는 0
	dijikstraQueue.push(startPos);
	best[S] = 0;

	while (dijikstraQueue.empty() == false) {
		Vertex curV = dijikstraQueue.top();
		dijikstraQueue.pop();

		// 현재 최고 기록과 비교하여 더 크다면 스킵
		if (best[curV.vertex] < curV.cost) continue;
		

		// 현재 지점에서 인접 경로를 포함하는 것이 최단 거리 인지를 판단
		for (int i = 0; i < adjacant[curV.vertex].size(); i++) {
			int there = adjacant[curV.vertex][i].vertex;
			int nextCost = best[curV.vertex] + adjacant[curV.vertex][i].cost; // 현재위치 최단 + 인접 경로 비용

			// 가격 비교
			if (nextCost >= best[there]) continue; // 인접 경로 목적지와 현재 최단 거리의 크기 비교


			// 발견 처리
			best[there] = nextCost;
			dijikstraQueue.push(Vertex{ there, nextCost });
		}

	}



}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	dijikstra();

	cout << best[D] << endl;
}

 

 

 

 

 

 

 line 70, if(nextCost >= best[there]) 이 코드에서 '='을 넣지 않아서가 이유였는데, 아마 테스트 케이스중에 같은 값의 최단 경로가 계속해서 나와서 다익스트라 큐를 메모리 초과 시키는것이 이유인 걸로 추측된다.

 

 

 

 

 

 여지껏 무조건 최소 비용이 더 작을 때만 갱신 하였는데 이젠 더 작거나 '같을' 때로 코드를 작성해야 할 듯 하다.