백준 5719번 [거의 최단 경로](C++) -yes6686- 티스토리

---

 

문제 링크 : https://www.acmicpc.net/problem/5719

 

 

이 문제를 푸는 사람들은 이미 다익스트라 알고리즘에 대해 이해했고 구현할 줄 아는 people일 거다.. 그쵸??

이 문제를 풀기 위해서는 생각이란 걸 하면 된다,,

 

[문제에서 거의 최단 경로는 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것이라고 한다.]

ㄴ이 문장을 읽고나서 대부분의 사람들은 머리가 띵~!하고 울렸을 것이다..

 

그렇다면 거의 최단 경로를 구하기 위해서는!

(일단 다익스트라 알고리즘을 이용해 시작점에서 도착점까지 최단경로로 가는 경로를 구한다.)

ㄴ경로를 vI벡터에 저장해줄건디.. 가장 짧은 경로만 저장해야하니께 더 작은 값이 나오면 vI[next].clear()를 해준다.

ㄴ그리고 최단 경로가 여러 개 있을 수 있기 때문에 dis[next]==ncost+cost의 경우도 저장해준당..

*참고로 역추적으로 간선들을 제거할예정이니 vI[]벡터에 예를들어 cur->next 방향을 next->cur로 반대 방향이 되게 저장해준다.

			if (dis[next] > ncost + cost) {
				dis[next] = ncost + cost;
				pq.push({ dis[next],next });
				vI[next].clear();
				vI[next].push_back(cur);
			}
			else if (dis[next] == ncost + cost) {
				vI[next].push_back(cur);
			}

 

(최단 경로의 정보를 얻었으니 역추적으로 각 간선들을 제거해준다.) 

ㄴ-1로 값을 변경한 것이 제거 한 거다.

**여기서 많은 분들이 이것을 안 해줘서 메모리초과를 받았을 것이다.

 

이것은 방문처리이다. 

ㄴvisited배열로 방문 처리를 해줘서 q에 같은 원소는 받지 않게 했다.

void eraser(int x) {
	q.push(x);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (visited[cur]) continue;
		visited[cur] = 1;
		for (int i = 0; i < vI[cur].size(); i++) {
			int next = vI[cur][i];
			for (int j = 0; j < v[next].size(); j++) {
				if (v[next][j].second == cur) {
					v[next][j].first = -1;
				}
			}
			q.push(next);
		}
	}
}

 

여기까지가 핵심이고 다시 djk()함수를 돌릴 때 -1값으로 변경한 것만 잘 예외처리하면 정답이 나온다

 

#include <iostream>
#include <string.h> //memset 사용할 거
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;

vector<pair<int, int>>v[501];
vector<int>vI[501]; // Inverse vector
int dis[501];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater< pair<int, int>>>pq;

void djk(int x,int n) {
	for (int i = 0; i < n; i++) {
		dis[i] = INF;
	}
	dis[x] = 0;
	pq.push({ dis[x],x });
	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int ncost = v[cur][i].first;
			int next = v[cur][i].second;
			if (ncost == -1) continue; 
			if (dis[next] > ncost + cost) {
				dis[next] = ncost + cost;
				pq.push({ dis[next],next });
				vI[next].clear();
				vI[next].push_back(cur);
			}
			else if (dis[next] == ncost + cost) {
				vI[next].push_back(cur);
			}
		}
	}
}

queue<int>q;
int visited[501];
void eraser(int x) {
	q.push(x);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (visited[cur]) continue;
		visited[cur] = 1;
		for (int i = 0; i < vI[cur].size(); i++) {
			int next = vI[cur][i];
			for (int j = 0; j < v[next].size(); j++) {
				if (v[next][j].second == cur) {
					v[next][j].first = -1;
				}
			}
			q.push(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	while (1) {
		int N, M;
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		int S, D;
		cin >> S >> D;
		int U, V, P;
		for (int i = 0; i < M; i++) {
			cin >> U >> V >> P;
			v[U].push_back({ P,V });
		}
		djk(S, N);
		eraser(D);
		djk(S, N);
		if (dis[D] == INF) {
			cout << -1 << '\n';
		}
		else {
			cout << dis[D] << '\n';
		}
		for (int i = 0; i < N; i++) {
			v[i].clear();
			vI[i].clear();
		}
		memset(visited, 0, sizeof(visited));
	}
}

 

 

편하게 댓글로 질문해 주세요~