algospot 선거 공약 (문제 ID: PROMISES) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PROMISES

algospot.com :: PROMISES

도시를 연결하는 고속도로들이 있다. 추가적인 고속도로 건설 계획에서 입력순서대로 고속도로를 건설한다 했을때

고속도로 건설의 정당성은 기존에 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결되거나, 두 도시를 오가는 데 걸리는 시간이 단축되는것, 둘 중 하나라도 만족해야 한다.

이때 정당성이 없는 고속도록 건설 계획의 개수를 구하는것이 문제이다.

 

경유할 수 있는 정점의 목록을 늘려가는 기존의 플로이드 알고리즘을 간선의 목록을 늘려가는 방식으로 변형하면 문제를 해결할 수 있다.

먼저 기존의 플로이드 알고리즘을 이용하여 이미 존재하는 고속도로들만을 이용한 최단경로를 계산한다.

그 후 입력 순서대로 건설 예정인 고속도로를 추가하는 앞에서 언급한 변형된 플로이드 알고리즘을 사용하여 최단거리 갱신 유무를 확인한 후 갱신 가능하다면 최단거리를 갱신한다.

이때 주의할점은 어느 방향으로 간선을 타고 갈 것인가를 정해야하기 때문에 정점을 추가할때와는 달리 경우의 수가 3개로 늘어난다.

 

	#include<iostream>
	#include<vector>
	using namespace std;
	const int INF = 987654321;
	int V, adj[200][200];
	// 기존 고속도로로 최단거리를 계산하는 플로이드 알고리즘
	void floyd() {
	for (int i = 0; i < V; i++)
	adj[i][i] = 0;
	for (int k = 0; k < V; k++)
	for (int i = 0; i < V; i++)
	for (int j = 0; j < V; j++)
	adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
	}
	// (a,b)를 연결하는 비용 c인 간선을 추가했을때의 adj를 적절히 갱신
	// 간선이 아무런 의미가 없을 경우 false반환
	bool update(int a, int b, int c) {
	if (adj[a][b] <= c)return false;
	for (int i = 0; i < V; i++)
	for (int j = 0; j < V; j++)
	// i~j의 최단경로가 (a,b)를 이용하려면
	// i~a-b~j or i~b-a~y의 형태를 가져야 한다.
	adj[i][j] = min(adj[i][j],
	min(adj[i][a] + c + adj[b][j],
	adj[i][b] + c + adj[a][j]));
	return true;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	for (int i = 0; i < 200; i++)
	for (int j = 0; j < 200; j++)
	adj[i][j] = INF;
	int m, n, result = 0;
	cin >> V >> m >> n;
	for (int i = 0; i < m; i++) {
	int src, des, cost;
	cin >> src >> des >> cost;
	adj[src][des] = min(adj[src][des], cost);
	adj[des][src] = min(adj[src][des], cost);
	}
	floyd();
	for (int i = 0; i < n; i++) {
	int src, des, cost;
	cin >> src >> des >> cost;
	if (!update(src, des, cost))
	result++;
	}
	cout << result << endl;
	}
	}

view raw algospot 선거 공약 (문제 ID: PROMISES).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/PROMISES.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2