C++[백준] 5719 거의 최단 경로

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

5719번: 거의 최단 경로

 

 

솔루션

---

처음에는 최단으로 도달 할 수 있는 경로 한개에 대해서만 방문하지 않도록 처리 하였는데, 알고보니, 최단 경로 모두 다 탐색하지 못하도록 하여야 한다.

 

1. 먼저 시작점을 기준으로 다익스트라를 돌리고,

 

2. dfs를 통해서, 특정 경로를 선택해서 목적지에 가중치가 넘지 않고 도달 가능하면 해당 경로를 bool 배열을 통해 true 로 바꿔준다.

 

3. 모든 최단 경로를 true로 바꿔줬다면, 다시 다익스트라를 돌린다. (이 때, 2.의 과정에서 true로 바꾼 경로에 대해서는 탐색하지 않는다.)

 

 

이렇게 하니, AC를 받았다.

 

dfs를 돌릴 때, 예외 처리의 순서가 잘 못 되어서 틀렸습니다를 받았다. 이점 주의!

 

 

 

코드

---

#define INF 987654321
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<pair<int, int>>V[502];
int N, M;
int dest, start;
bool is_visit[502][1004];


int weight[502];
void dijkstra() {
	
	for (int i = 0; i <= N; i++) weight[i] = INF;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0,start });
	weight[start] = 0;
	
	while (!pq.empty()) {
		int str = pq.top().second;
		int w = -pq.top().first;
		pq.pop();

		if (weight[str] < w) continue;

		for (int i = 0; i < V[str].size(); i++) {
			int next = V[str][i].first;
			int cost = w + V[str][i].second;

			if (is_visit[str][next] || weight[next] <= cost) continue;
			pq.push({ -cost,next });
			weight[next] = cost;
		}
	}
}

//0은 방문 X, 1은 방문을 했지만 경로 X, 2는 방문 했고, 길도 있음.
int is_travel[502];
bool travel(int str, int w) {
	if (w > weight[str]) return false;
	if (str == dest && w == weight[dest]) {
		return true;
	}
	else if (is_travel[str] == 1) {
		return false;
	}
	else if (is_travel[str] == 2) {
		return true;
	}

	is_travel[str] = 1;
	bool is_road = false;
	for (int i = 0; i < V[str].size(); i++) {
		int cost = w + V[str][i].second;
		int next = V[str][i].first;

		bool tmp = travel(next, cost);
		is_visit[str][next] = tmp;
		if (tmp) {
			is_travel[str] = 2;
			is_road = true;
		}
	}
	if (is_road) {
		return true;
	}
	return false;
}

void init() {
	for (int i = 0; i <= N; i++) {
		V[i].clear();
		is_travel[i] = 0;
		for (int j = 0; j <= M; j++) {
			is_visit[i][j] = false;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	while (true) {

		cin >> N >> M;
		if (N == M && N == 0) return 0;
		cin >> start >> dest;

		init();

		int str, end, w;
		for (int i = 0; i < M; i++) {
			cin >> str >> end >> w;
			V[str].push_back({ end,w });
		}

		dijkstra();
		travel(start, 0);
		dijkstra();

		if (weight[dest] == INF) cout << -1 << "\n";
		else cout << weight[dest] << "\n";
	}
}