[P5] 13308번 주유소 C++ 다익스트라, 다이나믹 프로그래밍

리뷰

 

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

다익스트라 + DP문제에 대해 어느정도 이해가 가기 시작했다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• p : 각 노드의 가중치들을 저장할 배열
• Edge : 이동할 노드와 가중치 등 간선 정보를 정의할 구조체, 간선 가중치를 기준으로 오름차순 정렬한다.
• edges : 간선 정보를 저장할 Edge타입 벡터 배열
• Pos : 현재 노드와 누적 연료 최소값, 누적 비용을 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

ll dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 1, p[1], 0 });
	vector<vector<ll>> dist(n + 1, vector<ll>(N, 1e11));
	dist[1][p[1]] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cf = pos.cf;
		ll cc = pos.cc;
		//cout << cn << " " << cf << " " << cc << "\n";
		if (cn == n) return cc;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn;
			int nf = min(cf, p[nn]);
			ll nc = cc + cf * edge.nv;

			if (dist[nn][nf] > nc) {
				dist[nn][nf] = nc;
				pq.push({ nn, nf, nc });
			}
		}
	}

	ll ans = 1e11;
	for (int i = 1; i <= N; ++i) ans = min(ans, dist[n][i]);
	return ans;
}

 

1번 노드에서 n번 노드까지의 최소 비용을 구하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, n개의 노드 가중치를 입력 받아 p배열에 저장해 준다.
2. m개의 간선 정보를 입력 받고, 인접 리스트 edges에 양방향 간선을 추가해 준다.
3. n개의 edges배열의 각 요소 벡터를 sort함수를 통해 오름차순으로 정렬해 준다.
4. dijkstra함수를 호출한다. 함수 내부엔 Pos타입의 우선순위 큐 pq를 초기화 하고, 초깃값 {1, p[1], 0}을 push해준다.
5. long long타입 2차원 벡터 dist를 n+1*N크기로 초기화 하고, 초기값은 2500^3이상으로 설정해 준다.
6. dist[1][p[1]]을 0으로 초기화 해줌으로 1번 노드에서 시작을 정의해 준다.
7. pq가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 변수 cn, cf, cc에 값을 파싱해준다.
8. 기저 조건으로 cn이 n인 경우 cc를 리턴해 준다.
9. edges[cn]을 순회하며 변수 nn에 다음노드를, nf에 cf, p[nn]중 작은 값을, nc에 cc + cf * 간선의 가중치를 저장한다.
10. dist[nn][nf]가 nc보다 클 경우 값을 갱신해 주고, nn, nf, nc를 pq에 push해준다.
11. 기저 조건에 도달할 때 까지 while루프를 수행하다가 dijkstra함수의 리턴값을 출력해 준다.

 

트러블 슈팅

1. pq에 너무 많은 요소가 push됨으로 인해 마지막 서브태스크에서 시간 초과가 발생하였다.
2. 간선의 가중치를 오름차순으로 정렬해 줌으로서 좀 더 그리디한 탐색을 통해 가지치기를 해주어 AC를 받았다.

 

참고 사항

1. dist벡터의 값은 누적 비용, 첫번째 인덱스는 노드 번호, 두번째 인덱스는 현재 경로 중 가장 싼 기름값이다.
2. 최악의 경우 누적 비용이 2500^3이 될 수 있으므로 이는 int범위를 넘어가기에 long long타입을 사용해 주었다.
3. pq에서 요소를 빼내었을때 노드 n일 경우 최적해 이므로 바로 리턴해 주면 된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 2501;
int n, m;
int p[N];
struct Edge {
	int nn, nv;
	bool operator<(const Edge& other) const {
		return nv < other.nv;
	}
};
vector<Edge> edges[N];
struct Pos {
	int cn, cf;
	ll cc;
	bool operator<(const Pos& other) const {
		return cc > other.cc;
	}
};

ll dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 1, p[1], 0 });
	vector<vector<ll>> dist(n + 1, vector<ll>(N, 1e11));
	dist[1][p[1]] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cf = pos.cf;
		ll cc = pos.cc;
		//cout << cn << " " << cf << " " << cc << "\n";
		if (cn == n) return cc;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn;
			int nf = min(cf, p[nn]);
			ll nc = cc + cf * edge.nv;

			if (dist[nn][nf] > nc) {
				dist[nn][nf] = nc;
				pq.push({ nn, nf, nc });
			}
		}
	}

	ll ans = 1e11;
	for (int i = 1; i <= N; ++i) ans = min(ans, dist[n][i]);
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	for (int i = 1; i <= n; ++i) sort(edges[i].begin(), edges[i].end());

	cout << dijkstra();
}