언제나 처음처럼

[문제 링크]

입력받는 버스 노선은 시작정점, 도착정점, 비용으로 이루어져 있다. 시작정점과 도착정점이 명시되어 있기 때문에 필자는 그래프를 무향그래프가 아닌 방향그래프로 만들었다.

또한 같은 노선이 여러개 존재할 수 있다고 명시되어 있기 때문에 이미 연결된 노선과 같은 노선이 입력으로 들어오면 기존 노선의 비용과 비교하여 더 적은 비용을 노선으로 선택하도록 구현하였다.

그래프를 만든 다음 플로이드-와샬 알고리즘을 수행하고 결과를 출력해주면 정답을 받을 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 987654321;
int n, m;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	for (int i = 1; i <= n; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (adj[a][b] == INF)
			adj[a][b] = c;
		else
			adj[a][b] = min(adj[a][b], c);
	}

	floyd();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (adj[i][j] == INF)
				cout << 0 << ' ';
			else
				cout << adj[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 165 day

[문제 링크]

정점들을 연결하는 간선의 가중치가 1인 그래프를 만든 다음, 모든 정점 간의 최단거리를 구하는 플로이드-와샬 알고리즘을 수행하고 모든 정점들의 케빈 베이컨 수를 계산하여 그 값이 가장 작은 인덱스를 출력하도록 구현하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 987654321;
int N, M;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	for (int i = 1; i <= N; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;

		adj[A][B] = 1;
		adj[B][A] = 1;
	}

	floyd();

	int temp = INF;
	int idx;
	for (int i = 1; i <= N; i++) {
		int kebin = 0;
		for (int j = 1; j <= N; j++)
			kebin += adj[i][j];

		if (temp > kebin) {
			temp = kebin;
			idx = i;
		}
	}

	cout << idx << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day