백준 13168 : 내일로 여행

www.acmicpc.net/problem/13168

13168번: 내일로 여행

이 문제는 문자열 처리 + 그래프 문제이다.

string 값으로 주어지는 역 이름을 인덱스화(?) 시켜주기 위하여 map자료 구조를 사용하였고 모든 역에서 모든 역으로 가는 최단 경로를 구하기 위하여 플로이드-워셜 알고리즘을 사용하였다. 내일로 티켓을 이용하는 경우와 이용하지 않는 경우의 비용을 저장하는 이차원 배열을 두개를 따로 만들어주어 저장했다. youth가 내일로 티켓을 이용하는 경우 비용을 저장한 배열인데 이 배열은 price / 2를 한 값을 저장해 줄 필요가 있어 버림이 일어나지 않도록 하기 위하여 실수값인 float 자료형으로 선언하였다.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

#define MAP unordered_map
const int INF = 200000;

MAP<string, int> city;
float youth[101][101];
int normal[101][101];
vector<string> wannago;
int n, youth_ticket_cost, m, k;

void floydwarshall() {
	string tmp, s_from, s_to;
	int from, to, normal_cost = 0;
	float youth_cost = youth_ticket_cost;

	for (int tmp = 0; tmp < city.size(); tmp++) {
		for (int from = 0; from < city.size(); from++) {
			for (int to = 0; to < city.size(); to++) {
				if (from == to) continue;
				if (youth[from][to] > youth[from][tmp] + youth[tmp][to]) {
					youth[from][to] = youth[from][tmp] + youth[tmp][to];
				}
				if (normal[from][to] > normal[from][tmp] + normal[tmp][to]) {
					normal[from][to] = normal[from][tmp] + normal[tmp][to];
				}
			}
		}
	}

	from = city[wannago[0]];
	for (int i = 1; i < wannago.size(); i++) {
		to = city[wannago[i]];
		youth_cost += youth[from][to];
		normal_cost += normal[from][to];
		from = to;
	}
	if (youth_cost < normal_cost) cout << "Yes";
	else cout << "No";
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string city_name, vehicle, s_from, s_to;
	int from, to, price, idx = 0;
	cin >> n >> youth_ticket_cost;
	while (n--) {
		cin >> city_name;
		if (city.find(city_name) == city.end()) {
			city[city_name] = idx;
			idx++;
		}
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> city_name;
		wannago.push_back(city_name);
	}
	for (int from = 0; from < city.size(); from++) {
		for (int to = 0; to < city.size(); to++) {
			if (from != to) {
				youth[from][to] = INF;
				normal[from][to] = INF;
			}
		}
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> vehicle >> s_from >> s_to >> price;
		from = city[s_from];
		to = city[s_to];
		if (from == to) continue;
		if (normal[from][to] > price) { normal[from][to] = price; normal[to][from] = price; }
		if (vehicle.compare("Mugunghwa") == 0 || vehicle.compare("ITX-Saemaeul") == 0 || vehicle.compare("ITX-Cheongchun") == 0) { youth[from][to] = 0; youth[to][from] = 0; }
		else if (vehicle.compare("V-Train") == 0 || vehicle.compare("S-Train") == 0) {
			if (youth[from][to] > float(price) / 2) { youth[from][to] = float(price) / 2; youth[to][from] = float(price) / 2; }
		}
		else {
			if (youth[from][to] > price) { youth[from][to] = price; youth[to][from] = price; }
		}
	}

	floydwarshall();

	return 0;
}

메모리: 2236 kb

시간: 8 ms