[정답이 아니라 풀이 기록입니다.]
유향그래프가 있다. s노드에서 e노드로 가는 최단 경로들이 있을때, 이 경로의 간선들을 이용하지 않는 최단 경로를 거의 최단 경로라고 한다. 거의 최단 경로의 길이를 구하여라
접근
- 최단 경로가 여러개라면 최단 경로들을 이루는 모든 간선을 이용 할 수 없습니다.
- 거의 최단 경로가 없을 수도 있습니다.
- 거의 최단 경로도 여러개 있을 수 있습니다.
- 최단경로, 거의 최단 경로 둘다 없을 수도 있습니다.
구현
최단 거리 구하기
최단 거리는 다익스트라를 통해서 구하면 되고
최단 거리와 노드를 같이 저장해야하기에 pair로 저장해야합니다.
STL 다익스트라는 큰것이 위로 올라오는 특성이 있기에 아래와 같이 선언해서 작은 것이 위로 올라오게 해줍니다.
priority_queue<pair<long long,long long>,vector<pair<long long, long long>>
,greater<pair<long long, long long>>> pq;
일단 기본 다익스트라를 만들어 봅니다.
pq.push({0LL,s});
while (!pq.empty()) {
long long value = pq.top().first;
int node = pq.top().second;
pq.pop();
if (value > D[node]) {
continue;
}
for (int i = 0; i < v[node].size(); i++) {
if (D[v[node][i].first] > value + v[node][i].second) {
D[v[node][i].first] = value + v[node][i].second;
pq.push({ D[v[node][i].first] ,v[node][i].first });
}
}
}그리고 이 문제에서는 최단 경로를 역추적해서 간선을 제거해야하기에 어떤 노드에서 갱신이 되었는지 기록해둬야 합니다
a노드에서 b노드가 갱신되었다
->시작점에서 b노드까지 올때 a를 통해 오는게 최단 경로이다.
이후에 만약 b가 도착지 노드를 갱신시킨다면?
->b는 도착지까지 가는 최단경로에 포함되고 b까지 오는 최단경로인 a도 포함된다.
기록과 제거는 대략적으로 위와 같이 이루어지는데 제거는 좀 이따 보기로하고 기록부터 보겠습니다.
기록
위에서 이야기했듯 a노드에서 b노드가 갱신되었다는 것은 시작점에서 b노드까지 올때 a를 통해 오는게 최단 경로이다는 것 입니다.
그리고 b지점까지 오는 최단 경로는 여러개 있을 수 있습니다.
그렇다면 b의 최단거리를 갱신시키는 노드는 1개지만, 최단거리가 같은 노드가 여러개 있을 수 있습니다.
시작점에서 a거쳐서 b = 10의 거리
시작점에서 c거쳐서 b = 10의 거리
이 경우 a,c 둘 다 최단 경로를 구성함
그렇기에 갱신의 기록은 컨테이너에 기록해야합니다.
저는 큐를 사용하였습니다.
만약 갱신이 일어난다면 이전의 기록은 필요 없기에 큐를 초기화하고 큐에 추가하고
최단거리가 같은 값이 들어온다면 큐에 추가해주는 방식입니다.
pq.push({0LL,s});
while (!pq.empty()) {
long long value = pq.top().first;
int node = pq.top().second;
pq.pop();
if (value > D[node]) {
continue;
}
for (int i = 0; i < v[node].size(); i++) {
if (D[v[node][i].first] > value + v[node][i].second) {
D[v[node][i].first] = value + v[node][i].second;
while (!check[v[node][i].first].empty()) {
check[v[node][i].first].pop();
}
check[v[node][i].first].push(node);
pq.push({ D[v[node][i].first] ,v[node][i].first });
}
else if (D[v[node][i].first] == value + v[node][i].second) {
check[v[node][i].first].push(node);
}
}
}역추적과 간선 제거
만약 시작점과 도착점이 연결되어있다면 기록을 하는 큐에 마치 그래프처럼 최단경로들로 연결이 되어 있을 것입니다.
그렇기에 도착점부터 시작점 방향으로 역추적을 하며 간선을 제거합니다
- 도착노드의 큐를 확인
- 큐에 있는 노드들을 a,b,c라 했을 때, a->도착지, b->도착지,c->도착지 간선을 제거 후
- a,b,c노드로 이동해 반복해서 확인
이런식으로 BFS와 같이 움직이며 제거합니다.
void del(int node) {
int top;
while (!check[node].empty()) {
top = check[node].front();
check[node].pop();
//제거
del(top);
}
}기본 코드는 위와 같습니다.
여기서 이제 top->node 간선을 제거해야합니다.
v[top]에서 lower_bound를 돌려 top->node 간선을 찾아내고 이를 erase로 제거하는 방식을 사용합니다.
bool comp(const pair<long long, long long> &a,const pair<long long, long long> &b) {
return a.first<b.first;
}
v[top].erase(lower_bound(v[top].begin(),v[top].end(),pair<long long, long long>(node,0),comp));(벡터가 pair로 이루어져있기에 비교함수를 커스텀해야합니다.)
제거의 전체적인 코드는 아래와 같습니다.
bool comp(const pair<long long, long long> &a,const pair<long long, long long> &b) {
return a.first<b.first;
}
void del(int node) {
int top;
while (!check[node].empty()) {
top = check[node].front();
check[node].pop();
v[top].erase(lower_bound(v[top].begin(),v[top].end(),
pair<long long, long long>(node,0),comp));
del(top);
}
}거의 최단 거리 구하기
일반 다익스트라로 최단거리를 구하면 됩니다.
최단 경로를 이루는 간선을 제거했기에 그냥 다익스트라로 구해지는 경로가 거의 최단 경로입니다.
pq.push({ 0LL,s });
while (!pq.empty()) {
long long value = pq.top().first;
int node = pq.top().second;
pq.pop();
if (value > AlmostD[node]) {
continue;
}
for (int i = 0; i < v[node].size(); i++) {
if (AlmostD[v[node][i].first] > value + v[node][i].second) {
AlmostD[v[node][i].first] = value + v[node][i].second;
pq.push({ AlmostD[v[node][i].first] ,v[node][i].first });
}
}
}답출력
최단 경로가 없다면 거의 최단 경로도 있을 수 없습니다.
그렇기에 D[도착지]가 INF라면 -1을 출력합니다.
D[도착지]가 INF가 아닐경우
AlmostD[도착지]가 INF라면 -1, 아니라면 AlmostD[도착지]를 출력하면 됩니다.
이것을 테스트 케이스마다 반복하면 되는데 벡터의 초기화, D,AlmostD의 초기화,큐의 초기화에 유의해야합니다.
마무리
역추적과 간선의 삭제가 복잡한 편입니다.
끝
