
리뷰

https://www.acmicpc.net/problem/17835
큐에 요소를 삽입하는 과정에서 N크기만큼 pq에 삽입하여 시간 초과를 받았다.
전역 변수
- N : 도시 관련 배열의 최대 크기를 정의할 상수 변수
- n : 도시의 개수를 저장할 변수
- m : 간선의 개수를 저장할 변수
- k : 면접장의 개수를 저장할 변수
- K : 면접장이 위치한 도시의 번호를 저장할 배열
- Edge : 간선 정보를 정의할 구조체
- edges : 간선 정보를 인접리스트로 정의할 벡터 배열
- P : 시뮬레이션 정보를 정의할 구조체, 거리를 기준으로 오름차순 정렬한다.
함수
1. dijkstra
pair<int, ll> dijkstra() {
priority_queue<P> pq;
vector<ll> dist(n + 1, 1e11);
for (int i = 0; i < k; ++i) {
pq.push({ K[i], 0 });
dist[K[i]] = 0;
}
while (!pq.empty()) {
P p = pq.top(); pq.pop();
int cn = p.cn;
ll cv = p.cv;
if (dist[cn] < cv) continue;
for (const Edge& next : edges[cn]) {
int nn = next.nn;
ll nv = next.nv;
if (dist[nn] > cv + nv) {
dist[nn] = cv + nv;
pq.push({ nn, cv + nv });
}
}
}
auto it = max_element(dist.begin() + 1, dist.end());
return { it - dist.begin(), *it };
}
다익스트라를 수행하여 면접장으로 부터 가장 먼 도시의 번호와 거리를 구하는 함수
문제풀이
- n, m, k값을 입력 받고, m개의 단방향 간선을 edges배열에 저장해 준다. 단, b와 a를 서로 바꾸어 준다.
- k개의 면접장 도시 번호를 입력 받아 K배열에 입력해 준다.
- dijktra함수를 호출하여 P타입의 우선순위 큐 pq를 초기화 해준다.
- 정수형 벡터 dist를 n + 1크기로, 값은 10억보다 크게끔 초기화 해준다.
- K배열을 순회하며 각 면접장 도시 번호와 초기 거리 0을 pq에 삽입해 주고, 해당 번호의 dist값을 0으로 변경한다.
- pq를 순회하며 다익스트라 알고리즘을 통해 각 도시로 이동할 수 있는 최단 거리를 구해준다.
- 변수 it에 max_element함수를 통해 dist에서 가장 큰 값의 이터레이터를 저장해 준다.
- it의 인덱스와 값을 리턴해 준 뒤 해당 값을 변수 res에 저장해 준다.
- res에 저장된 값을 순차적으로 줄바꿈을 통해 출력해 준다.
트러블 슈팅
- pq에 K배열의 값을 추가해 줄때 k개의 요소가 아닌 foreach로 추가하여 pq가 터져 시간 초과를 받았다.
- k개의 요소만 pq에 삽입, dist의 거리를 0으로 저장하여 AC를 받았다.
참고 사항
- 각 도시에서 면접장이 아닌 면접장에서 도시까지의 최단 거리를 구해주어야 한다.
- 이를 위해 인접 리스트를 초기화 할 때 도시 번호를 역순으로 변경하여 저장해 주어야 한다.
- max_element를 사용할 때 dist.begin() + 1부터 수행해 주어야 dist[0]에 담긴 매우 큰 값을 무시할 수 있다.
- 혹은 dist[0]을 0으로 초기화 후 dist의 begin()부터 end()까지 순회해 주면 된다.
정답 코드
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 100001;
int n, m, k;
int K[N];
struct Edge {
int nn;
ll nv;
};
vector<Edge> edges[N];
struct P {
int cn;
ll cv;
bool operator<(const P& other) const {
return cv > other.cv;
}
};
pair<int, ll> dijkstra() {
priority_queue<P> pq;
vector<ll> dist(n + 1, 1e11);
for (int i = 0; i < k; ++i) {
pq.push({ K[i], 0 });
dist[K[i]] = 0;
}
while (!pq.empty()) {
P p = pq.top(); pq.pop();
int cn = p.cn;
ll cv = p.cv;
if (dist[cn] < cv) continue;
for (const Edge& next : edges[cn]) {
int nn = next.nn;
ll nv = next.nv;
if (dist[nn] > cv + nv) {
dist[nn] = cv + nv;
pq.push({ nn, cv + nv });
}
}
}
auto it = max_element(dist.begin() + 1, dist.end());
return { it - dist.begin(), *it };
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
while (m--) {
int a, b, c; cin >> a >> b >> c;
edges[b].push_back({ a, c });
}
for (int i = 0; i < k; ++i) cin >> K[i];
auto res = dijkstra();
cout << res.first << "\n" << res.second;
}
728x90
'알고리즘 공부 > C++' 카테고리의 다른 글
[G4] 백준 22116번 창영이와 퇴근 C++ 다익스트라 (0) | 2025.04.14 |
---|---|
[G2] 백준 1486번 등산 C++ 다익스트라, 정렬 (0) | 2025.04.13 |
[P4] 백준 17481번 최애 정하기 C++ 이분 매칭, 해시맵 (1) | 2025.04.10 |
[P4] 백준 1298번 노트북의 주인을 찾아서 C++ 이분 매칭 (0) | 2025.04.09 |
[P4] 백준 2188번 축사 배정 C++ 이분 매칭 (0) | 2025.04.08 |