BOJ - 5972번 택배 배송

문제 출처: https://www.acmicpc.net/problem/5972

문제 난이도

Gold 5

문제 접근법

다익스트라 이용하는 대표 문제!

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 987654321

using namespace std;

vector<pair<int, int>> arr[50001];
int dp[50001];

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
		arr[b].push_back({ a,c });
	}
	for (int i = 1; i <= N; i++) {
		dp[i] = INF;
	}
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({ 0,1 });
	dp[1] = 0;
	while (!pq.empty()) {
		int cost = pq.top().first;
		int idx = pq.top().second;
		pq.pop();
        if(dp[idx] < cost) continue;
		for (int k = 0; k < arr[idx].size(); k++) {
			int nextN = arr[idx][k].first;
			int nextCost = arr[idx][k].second;
			if (dp[nextN] > nextCost + cost) {
				dp[nextN] = nextCost + cost;
                pq.push({ dp[nextN],nextN });
			}
		}
	}

	cout << dp[N] << "\n";
	return 0;
}

if(dp[idx]<cost) continue; 대신 bool check[50001] 배열로 check해도 통과한다.

피드백

첨에 if(dp[nextN] > nextCost + cost) 조건문에 pq.push를 넣지 않고 바깥에서 넣었더니 메모리초과나 시간초과가 났다. 주의!