[백준/BOJ] 백준 13168번 : 내일로 여행

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

13168번: 내일로 여행

cost1[][]에 내일로 티켓을 사지 않을 경우 [도시1][도시2]사이 직접 연결된 최소 비용을 저장하고, cost2[][]에 내일로 티켓을 살 경우 [도시1][도시2]사이 직접 연결된 최소 비용을 저장한 뒤, 플로이드 알고리즘을 이용해 최소 이동 비용을 구해서 이를 이용해 문제를 해결했다. 50% 할인의 표현은, 50% 할인이 아닌 비용(100% 비용)의 비용은 2를 곱해서 나머지 비용(50% 할인 비용)은 50% 할인효과가 나도록 구현했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
using namespace std;

int n, r;
int m;
int k;
vector<string> order;
unordered_map<string, int> city_id;

int cost1[101][101]; //내일로 티켓을 사지 않을 경우 [도시1][도시2]사이 직접 연결된 최소 비용
int cost2[101][101]; //내일로 티켓을 살 경우 [도시1][도시2]사이 직접 연결된 최소 비용

void Pre()
{
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
		{
			cost1[i][j] = 987654321;
			cost2[i][j] = 987654321;
		}
}

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

	Pre();

	cin >> n >> r;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		city_id.insert(make_pair(input, i));
	}

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		string input;
		cin >> input;

		order.push_back(input);
	}

	cin >> k;

	cin.ignore();

	for (int i = 0; i < k; i++)
	{
		string input1;

		getline(cin, input1);

		vector<string> input2;
		stringstream ss(input1);
		string temp;
		while (getline(ss, temp, ' '))
		{
			input2.push_back(temp);
		}

		int start_city = city_id[input2[1]];
		int end_city = city_id[input2[2]];

		//내일로 티켓을 사지 않을 경우
		cost1[start_city][end_city] = min(cost1[start_city][end_city], stoi(input2[3]) * 2);
		cost1[end_city][start_city] = min(cost1[end_city][start_city], stoi(input2[3]) * 2);

		cost2[start_city][end_city] = min(cost2[start_city][end_city], stoi(input2[3]) * 2);
		cost2[end_city][start_city] = min(cost2[end_city][start_city], stoi(input2[3]) * 2);

		//내일로 티켓을 사는 경우
		if (input2[0] == "Mugunghwa" || input2[0] == "ITX-Saemaeul" || input2[0] == "ITX-Cheongchun")
		{
			cost2[start_city][end_city] = 0;
			cost2[end_city][start_city] = 0;
		}

		else if (input2[0] == "S-Train" || input2[0] == "V-Train")
		{
			//50%할인이 아닌 100%가격은 *2를 하여서, 50%할인의 효과
			cost2[start_city][end_city] = min(cost2[start_city][end_city], stoi(input2[3]));
			cost2[end_city][start_city] = min(cost2[end_city][start_city], stoi(input2[3]));
		}

		else
		{
			cost2[start_city][end_city] = min(cost2[start_city][end_city], stoi(input2[3]) * 2);
			cost2[end_city][start_city] = min(cost2[end_city][start_city], stoi(input2[3]) * 2);
		}

	}

	for (int i = 0; i < n; i++)
	{
		cost1[i][i] = 0;
		cost2[i][i] = 0;
	}

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if ((cost1[i][k] != 987654321) && (cost1[k][j] != 987654321))
					cost1[i][j] = min(cost1[i][j], cost1[i][k] + cost1[k][j]);
				if ((cost2[i][k] != 987654321) && (cost2[k][j] != 987654321))
					cost2[i][j] = min(cost2[i][j], cost2[i][k] + cost2[k][j]);
			}

	int result1 = 0;
	int result2 = 0;

	for (int i = 0; i < order.size() - 1; i++)
	{
		int here_city_id = city_id[order[i]];
		int there_city_id = city_id[order[i + 1]];

		result1 += (cost1[here_city_id][there_city_id]);
		result2 += (cost2[here_city_id][there_city_id]);
	}

	result2 += (r * 2);

	if (result1 > result2)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}