Week6 - Floyd Warshall

#include<iostream>

using namespace std;
const int MAX = 9900000;

int min(int a, int b) {
	return (a < b) ? a : b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	int cost[101][101];
	cin >> n >> m;

	fill_n(cost[0], 101 * 101, MAX + 1);
	for (int i = 1; i <= n; i++) {
		cost[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int from;
		int to;
		int c;
		cin >> from >> to >> c;
		cost[from][to] = min(cost[from][to], c);
	}

	for (int i = 1; i <= n; i++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {
				if (cost[from][to] > cost[from][i] + cost[i][to])
					cost[from][to] = cost[from][i] + cost[i][to];
			}
		}
	}

	for (int from = 1; from <= n; from++) {
		for (int to = 1; to <= n; to++) {
			// 갈 수 없을 경우 0으로 표시
			cout << ((cost[from][to] > MAX) ? 0 : cost[from][to]) << " ";
		}
		cout << "\n";
	}
}

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

int max(int a, int b) {
	return (a > b) ? a : b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	int score[51][51];
	pair<int, int> max_score[51];
	queue<int> candidate;
	cin >> n;

	fill_n(score[0], 51 * 51, n - 1);
	for (int i = 1; i <= n; i++) {
		score[i][i] = 0;
		max_score[i] = { i,0 };
	}

	while (true) {
		int a, b;
		cin >> a >> b;
		if (a == -1) break;
		score[a][b] = 1;
		score[b][a] = 1;
	}

	// from~to의 최단경로 각각 구하기
	for (int i = 1; i <= n; i++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {
				if (score[from][to] > score[from][i] + score[i][to])
					score[from][to] = score[from][i] + score[i][to];
			}
		}
	}

	// 각 정점에 대해 다른 모든 정점과의 거리 중 가장 먼 값 구하기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			max_score[i].second = max(max_score[i].second, score[i][j]);
		}
	}

	// 점수 오름차순으로 정렬
	sort(max_score + 1, max_score + n + 1, compare);

	// 회장 후보만 큐에 넣음
	candidate.push(max_score[1].first);
	for (int i = 2; i <= n; i++) {
		if (max_score[1].second == max_score[i].second) candidate.push(max_score[i].first);
		else break;
	}

	cout << max_score[1].second << " " << candidate.size() << "\n";
	while (!candidate.empty()) {
		cout << candidate.front() << " ";
		candidate.pop();
	}
}

#include<iostream>
#include<string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	bool equal[26][26];
	char result[10];
	cin >> n;
	cin.ignore(32767, '\n');

	fill_n(equal[0], 26 * 26, false);

	// 전제 입력받기
	for (int i = 0; i < n; i++) {
		string premise;
		getline(cin, premise);
		int first = premise.front() - 'a';
		int second = premise.back() - 'a';
		equal[first][second] = true;
		equal[first][first] = true;
		equal[second][second] = true;
	}

	// n단 논법
	for (int i = 0; i < 26; i++) {
		for (int first = 0; first < 26; first++) {
			for (int second = 0; second < 26; second++) {
				if (equal[first][i] && equal[i][second]) {
					equal[first][second] = true;
				}
			}
		}
	}

	cin >> m;
	cin.ignore(32767, '\n');

	for (int i = 0; i < m; i++) {
		string premise;
		getline(cin, premise);
		int first = premise.front() - 'a';
		int second = premise.back() - 'a';
		result[i] = (equal[first][second]) ? 'T' : 'F';
	}

	for (int i = 0; i < m; i++) {
		cout << result[i] << "\n";
	}
}