[G1] 백준 1884번 고속도로 C++ 다익스트라

리뷰

 

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

다익스트라이지만 고려해야할 요소가 거리 뿐만이 아닌 문제

 

 

전역 변수

• k : 교통비의 값을 저장할 변수
• n : 도시의 개수를 저장할 변수
• r : 도로의 개수를 저장할 변수
• Edge : 간선 정보 다음 노드 nn, 도로의 길이 l, 도로의 통행료 t를 정의할 구조체
• edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열
• Pos : 시뮬레이션 정보 현재 노드 cn, 현재 길이 cl, 현재까지의 통행료 ct를 정의할 구조체, cl이 동일하면 ct가 작은 순서대로, 아니라면 cl이 작은 순서대로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra()

 

다익스트라를 통해 통행료 한도 내에서 1번 도시에서 N번 도시까지 가는 최단 거리를 구하는 함수

1. Pos타입 우선순위 큐 pq를 초기화 하고, 초깃값 {1, 0, 0}을 psuh 해준다.
2. pii타입의 2차원 벡터 best를 n + 1크기로 초기화 해주고, best[1]에 {0, 0}을 push해준다.
3. pq가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 현재까지의 거리 + 간선의 거리를 더한 값을 변수 nl로 저장해 준다.
5. 현재까지의 통행료 + 간선의 통행료를 더한 값을 변수 nt로 저장해 준다.
6. 만약 nt가 k보다 커졌을 경우 continue처리해 준다. 아니라면 변수 flag를 초깃값 false로 초기화 해준다.
7. best[nn]을 순회하며 nl과 nt가 기존의 것 보다 모두 크거나 같다면 flag를 true로 변경 후 break해준다.
8. 기존의 nl과 nt가 현재의 nl, nt보다 모두 크다면 해당 값을 erase처리해 준다.
9. 탐색을 마친 후 flag의 값이 여전히 false라면, nl, nt를 best[nn]에 push해주고, pq에 nn, nl, nt를 push해준다.
10. while루프가 종료된 후 best[n]을 오름차순으로 정렬하고, 만약 best[n]이 비었다면 -1을, 아니라면 가장 처음 요소의 nl값을 리턴해 준다.

 

문제풀이

1. k, n, r에 각각의 값을 입력 받아준다.
2. r개의 간선 정보를 입력 받아 edges배열에 단방향으로 추가해 준다.
3. dijkstra함수를 호출하고 리턴받은 값을 출력해 준다.

 

트러블 슈팅

• 다익스트라 함수 내부에서 단순히 최단 거리를 구하면서도 비용이 k이내일 경우 pq에는 push가 되도록 구현했었으나 54%에서 Fail을 받았다.
• 거리, 통행료를 모두 고려하며 그 중에서도 최악의 경우의 간선은 제거해 주는 방식으로 구현하니 AC를 받았다.

 

참고 사항

• 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다.
• 각 도로는 일방통행로이다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define pii pair<int, int>
using namespace std;

int k, n, r;
struct Edge {
	int nn, l, t;
};
vector<Edge> edges[101];
struct Pos {
	int cn, cl, ct;
	bool operator<(const Pos& other) const {
		if (cl == other.cl) return ct > other.ct;
		return cl > other.cl;
	}
};

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 1, 0, 0 });
	vector<vector<pii>> best(n + 1);
	best[1].push_back({ 0, 0 });

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cl = pos.cl, ct = pos.ct;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nl = cl + edge.l, nt = ct + edge.t;

			if (nt > k) continue;
			bool flag = false;
			for (auto it = best[nn].begin(); it != best[nn].end();) {
				if ((*it).first <= nl && (*it).second <= nt) {
					flag = true;
					break;
				}
				else if ((*it).first > nl && (*it).second > nt) {
					it = best[nn].erase(it);
				}
				else it++;
			}
			if (!flag) {
				best[nn].push_back({ nl, nt });
				pq.push({ nn, nl, nt });
			}
		}
	}
	sort(best[n].begin(), best[n].end());
	return best[n].empty() ? -1 : best[n][0].first;
}

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

	cin >> k >> n >> r;
	while (r--) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		edges[a].push_back({ b, c, d });
	}

	cout << dijkstra();
}