백준 5710 거의 최단 경로 (c++) : 피너클

5719번: 거의 최단 경로

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

다익스트라 문제다.

 

다익스트라로 최단 경로를 구하며 vector<int>parent에 지금 정점 이전 정점들을 집어넣고

parent에서 구해진 정점들 간의 연결을 전부 끊어준다음

다시 다익스트라를 돌릴것이다.

 

long long n, m, s, d;
vector<pair<long long, long long>> graph[501];
long long dist[501];
long long visited[501][501];

vector<int> parent[501];

사용하는 변수들이다.

while (true) {
	cin >> n >> m;
	if (n == 0 && m == 0) break;
	
	for (int i = 0; i < 501; i++) {
		for (int j = 0; j < 501; j++) {
			visited[i][j] = false;
		}
		graph[i].clear();
		parent[i].clear();
	}
	cin >> s >> d;
	for (int i = 0; i < m; i++) {
		long long u, v, p;
		cin >> u >> v >> p;
		graph[u].push_back({ v, p });

		visited[u][v] = true;
	}

입력 부분이다.

visited, graph, parent 전부 초기화 해주는거 잊으면 안된다. 나는 parent 초기화 하는거 잊어서 많이 틀렸다.

visited는 내가 변수 명을 잘못 썻는데 그래프라 생각하면 된다.

visited[5][10] = true면 5에서 10으로 갈 수 있다는 것이다.

 

		for (int i = 0; i < n; i++) dist[i] = 987654321;
		dijkstra(s);

		for (int i = 0; i < n; i++) dist[i] = 987654321;
		remove_dijkstra(d);
		
		for (int i = 0; i < n; i++) dist[i] = 987654321;
		dijkstra(s);

그 후에는 다익스트라 돌리고

다익스트라 돌린걸로 지워준다음에

다시 다익스트라 돌리면 된다.

 

void dijkstra(long long start) {
	dist[start] = 0;
	priority_queue<pair<long long, long long>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		long long now = pq.top().second;
		long long now_distance = -pq.top().first;
		pq.pop();

		if (dist[now] < now_distance) continue;

		for (long long i = 0; i < graph[now].size(); i++) {
			long long next = graph[now][i].first;
			long long next_distance = graph[now][i].second;

			if (!visited[now][next]) continue;

			if (now_distance + next_distance == dist[next]) {
				parent[next].push_back(now);
			}
			else if (now_distance + next_distance < dist[next]) {
				parent[next].clear();
				parent[next].push_back(now);
				dist[next] = now_distance + next_distance;
				pq.push({ -dist[next], next });
			}
		}
	}
}

다익스트라다.

전부 기본 다익스트라랑 같지만

			if (now_distance + next_distance == dist[next]) {
				parent[next].push_back(now);
			}
			else if (now_distance + next_distance < dist[next]) {
				parent[next].clear();
				parent[next].push_back(now);
				dist[next] = now_distance + next_distance;
				pq.push({ -dist[next], next });
			}

이것들을 추가해줘야한다.

현재 정점에서 다음 정점으로 가는 비용이 기존에 비용과 같으면 

parent[next]에 현재 정점을 넣어준다.

이렇게 하면 parent[next]안에는 next이전의 정점들이 모이게 된다.

만약 지금 비용이 기존 비용보다 더 싸다면

parent[next]를 초기화하고 넣어주면 된다.

		for (long long i = 0; i < graph[now].size(); i++) {
			long long next = graph[now][i].first;
			long long next_distance = graph[now][i].second;

			if (!visited[now][next]) continue;

visited는 아까도 말했지만 갈수있는지이다. now에서 next로 못가면 그냥 지나간다.

 

void remove_dijkstra(int end) {
	queue<int> q;
	q.push(end);
	bool vvisited[501] = { false, };
	vvisited[end] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < parent[now].size(); i++){
			int next = parent[now][i];

			visited[next][now] = false;

			if (!vvisited[next]) {
				vvisited[next] = true;
				q.push(next);
			}
			
		}
	}
}

visited를 제거하는 함수이다.

parent에는 해당 정점 이전의 정점들이 모여있다.

즉 now는 지금의 정점이고 next는 이전의 정점들이다.

next -> now로 이동한다.

그러니 visited[next][now]를 false로 해준다.

그 뒤로는 bfs와 같다.

		for (int i = 0; i < n; i++) dist[i] = 987654321;
		dijkstra(s);

		for (int i = 0; i < n; i++) dist[i] = 987654321;
		remove_dijkstra(d);
		
		for (int i = 0; i < n; i++) dist[i] = 987654321;
		dijkstra(s);

이렇게 remove까지 하고 다익스트라를 한번 더 돌려준뒤

		if (dist[d] == 987654321) cout << -1 << '\n';
		else cout << dist[d] << '\n';
	}

dist가 987654321이라면 도달하지 못했다는 것이다. -1을 출력한다.

아니면 바로 출력한다.