[백준 8452] 그래프와 쿼리 (C++)

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

8452번: 그래프와 쿼리

1. 주의할 점

- 오프라인 쿼리의 원리를 활용한다(간선을 끊는게 아닌 쿼리의 역으로 실행하여 간선을 추가하는 방향으로)

- Dijkstra를 통해 1번 노드에서 다른 Node까지의 최단 거리를 구한다

- 가장 처음에만 Dist를 MAX 값으로 모두 초기화 한다

 

2. 구현

- 간선과 쿼리의 정보를 모두 받고, 만약 입력받은 쿼리의 정보 중, U를 입력 받는다면 뒤 번호의 간선의 가중치를 0으로 둔다

- 모든 간선 중에서 가중치가 0이 아닌 간선을 V[] 벡터에 반대편 Node 번호를 추가한다

- 쿼리의 역순으로 수행하며, 쿼리의 값 중에서 U를 포함한다면 3가지 동작을 한다

(1) 간선을 추가

(2) 추가된 간선에 따라 간선의 양끝점에 대한 Dist값이 변하는지 확인한다 (if (dist[end] <= dist[start] + 1) continue;)

(3) Dist값이 초기화된다면, 추가된 간선의 끝점에 대해 Dijsktra를 수행한다

- 쿼리 값에 E가 포함된다면 Dist값을 Ans 벡터에 추가한다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct info {
	int s, e, val;
};
struct info2 {
	char order;
	int num;
};
info tmp;
info2 tmp2;
int n, m, q, st, en;
int dist[1001];
vector<info> edge[100001];
vector<info2> query[200001];
vector<int> ans;
vector<int> v[1001];

void dijkstra(int ii) {
	queue<int> q;
	q.push(ii);
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			if (dist[v[cidx][i]] > dist[cidx] + 1) {
				dist[v[cidx][i]] = dist[cidx] + 1;
				q.push(v[cidx][i]);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> st >> en;
		tmp.s = st;
		tmp.e = en;
		tmp.val = 1;
		edge[i].push_back(tmp);
	}
	for (int i = 1; i <= q; i++) {
		char c;
		int a;
		cin >> c >> a;
		tmp2.num = a;
		tmp2.order = c;
		query[i].push_back(tmp2);
		if (c == 'U')
			edge[a][0].val = 0;
	}
	for (int i = 1; i <= m; i++) {
		if (edge[i][0].val == 0) continue;
		int start = edge[i][0].s;
		int end = edge[i][0].e;
		v[start].push_back(end);
	}
	for (int i = 1; i <= n; i++)
		dist[i] = MAX;
	dist[1] = 0;
	dijkstra(1);
	for (int i = q ; i > 0; i--) {
		if (query[i][0].order == 'U') {
			int vv = query[i][0].num;
			int start = edge[vv][0].s;
			int end = edge[vv][0].e;
			v[start].push_back(end);
			if (dist[end] <= dist[start] + 1) continue;		//어차피 최단경로 갱신 안되는 경우
			dist[end] = dist[start] + 1;
			dijkstra(end);
		}
		else {
			int temp = dist[query[i][0].num] == MAX ? -1 : dist[query[i][0].num];
			ans.push_back(temp);
		}
	}
	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << '\n';
	system("pause");
	return 0;
}