BOJ 5719 - 거의 최단 경로 (다익스트라)

https://suuntree.tistory.com/120?category=797985참고

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

참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다.

 

<문제설명>

최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라

 

<풀이>

1) 다익스트라https://suuntree.tistory.com/120?category=797985참고

 

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

 

참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다.

 

 

 

<문제설명>

출발점 s에서 도착점 e로 갈때, 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라

 

 

<풀이>

1) 다익스트라를 적용해서 dist배열을 초기화 한다.

 

2) 도착점 부터 역방향 인접배열를 사용해서 모든 간선을 탐색하는 dfs를 수행한다.

이 과정에서 dist[curr] + adj[curr][prv] = dist[prv] 인 경우 해당 간선을 사용하지 않는다는 표시를 한다. (blocked 배열)

void setBlocked(int u, int p) {
	//이 간선이 사용할 수 없는 간선인지?
	//사용할 수 있는 간선인 경우 더이상 이 간선을 따라 dfs하지 않는다
	if (u != e) {
		if (dist[u] + adj[u][p] == dist[p])
			blocked[u][p] = true;
		if (!blocked[u][p])
			return;
	}
	//간선에 대한 dfs이므로 vst배열로 걸러주는 작업을 여기서 한다.
	if (vst[u]) return;
	vst[u] = true;

	for (int v = 0, w; v < n; v++) {
		w = radj[u][v];
		if (w == INF) continue;
		setBlocked(v, u);
	}
}

 

3) 다시 다익스트라를 하되, blocked에 체크된 간선은 사용하지 않는다.

 

<코드>

typedef pair<int, int> P;
const int MAX = 5e2 + 2;
const int INF = 1e9;

bool blocked[MAX][MAX], chk[MAX], vst[MAX];
int adj[MAX][MAX], radj[MAX][MAX];
int dist[MAX], n, m, s, e;

void setBlocked(int u, int p) {
	if (u != e) {
		if (dist[u] + adj[u][p] == dist[p])
			blocked[u][p] = true;
		if (!blocked[u][p])
			return;
	}
	if (vst[u]) return;
	vst[u] = true;

	for (int v = 0, w; v < n; v++) {
		w = radj[u][v];
		if (w == INF) continue;
		setBlocked(v, u);
	}
}

int main() {
	FAST;
	while (true) {
		fill(&adj[0][0], &adj[MAX - 1][MAX], INF);
		fill(&radj[0][0], &radj[MAX - 1][MAX], INF);
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		cin >> s >> e;
		for (int i = 0, u, v, w; i < m; i++) {
			cin >> u >> v >> w;
			adj[u][v] = w;
			radj[v][u] = w;
		}
///////////////////첫번째 다익스트라/////////////////////
		fill(dist, dist + MAX, INF);
		memset(chk, 0, sizeof(chk));
		dist[s] = 0;
		priority_queue<P, vector<P>, greater<P>> pq;
		pq.push({ dist[s],s });

		while (!pq.empty()) {
			int u = pq.top().second; pq.pop();
			if (chk[u]) continue;
			chk[u] = true;

			for (int v = 0, w; v < n; v++) {
				w = adj[u][v];
				if (w == INF) continue;
				if (dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w;
					pq.push({ dist[v],v });
				}
			}
		}

////////////////blocked배열 초기화////////////////////
		memset(blocked, false, sizeof(blocked));
		memset(vst, false, sizeof(vst));
		setBlocked(e, -1);

///////////////////두번째 다익스트라/////////////////////
		fill(dist, dist + MAX, INF);
		memset(chk, 0, sizeof(chk));
		dist[s] = 0;
		pq.push({ dist[s],s });

		while (!pq.empty()) {
			int u = pq.top().second; pq.pop();
			if (chk[u]) continue;
			chk[u] = true;

			for (int v = 0, w; v < n; v++) {
				w = adj[u][v];
				if (w == INF || blocked[u][v]) continue;
				if (dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w;
					pq.push({ dist[v],v });
				}
			}
		}

		cout << (dist[e] == INF ? -1 : dist[e]) << '\n';
	}
}

 

<생각>

임계경로 문제풀면서 나중에 유용하게 쓰일거라고 생각했던 아이디어를 적용할 수 있어서 좋았다.