문제 풀이

내일로 티켓을 이용했을때와 이용하지 않았을때의 요금을 비교해서 내일로 티켓을 사는것이 더 좋으면 'Yes' 출력 그 외의 경우는 'No' 출력하는 문제.
내일로는 ITX-새마을, ITX-청춘 무료이용, S-Train, V-Train 반값 이용 가능하다.
각 도시 이름에 map을 이용해서 번호를 부여해주고 여행 일정대로 차례로 요금을 계산한다.
방문하는 도시에서 다음 방문하는 도시까지 가는 최소 요금을 모두 알아야하니까 플로이드-와샬 알고리즘을 이용한다. 이 때, 내일로를 이용했을 때 최소요금을 계산하여 저장할 배열과 내일로를 이용하지 않았을 때 최소요금을 계산하여 저장할 배열 각각에 대해 플로이드-와샬 알고리즘을 적용해준다.

문제 링크

boj/13168

소스코드

PS/13168.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<float.h>
using namespace std;
vector<string> tour;
map<string, int> cities_num;
double arr[101][101];
double arr2[101][101];
double d[101][101];
double d2[101][101];
int main()
{
	int n, r,m,k;
	cin >> n >> r;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		cities_num[s] = i+1;
	}
	for (int i = 1; i < 101; i++)
	{
		for (int j = 1; j < 101; j++)
		{
			if (i == j)
			{
				arr[i][j] = 0;
				arr2[i][j] = 0;
			}
			else
			{
				arr[i][j] = DBL_MAX;
				arr2[i][j] = DBL_MAX;
			}
		}
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		string s;
		cin >> s;
		tour.push_back(s);
	}
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		string train, f, t;
		double c;
		cin >> train >> f >> t >> c;
		if (train == "Mugunghwa" || train == "ITX-Saemaeul" || train == "ITX-Cheongchun" || train == "S-Train" || train == "V-Train")
		{
			if (train == "S-Train" || train == "V-Train")
			{
				if(arr2[cities_num[f]][cities_num[t]] > c/2.0)
				arr2[cities_num[f]][cities_num[t]]= c / 2.0;
				if (arr2[cities_num[t]][cities_num[f]] > c / 2.0)
				arr2[cities_num[t]][cities_num[f]] = c / 2.0;
			}
			else
			{
				arr2[cities_num[f]][cities_num[t]] = 0;
				arr2[cities_num[t]][cities_num[f]] = 0;
			}
		}
		else
		{
			if (arr2[cities_num[f]][cities_num[t]] > c)
			arr2[cities_num[f]][cities_num[t]] = c;
			if (arr2[cities_num[t]][cities_num[f]] > c)
			arr2[cities_num[t]][cities_num[f]] = c;
		}
		if(arr[cities_num[f]][cities_num[t]] > c)
			arr[cities_num[f]][cities_num[t]] = c;
		if(arr[cities_num[t]][cities_num[f]] > c)
			arr[cities_num[t]][cities_num[f]] = c;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			d[i][j] = arr[i][j];
			d2[i][j] = arr2[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= n; k++)
			{
				if (d[j][k] > d[j][i] + d[i][k])
					d[j][k] = d[j][i] + d[i][k];
				if (d2[j][k] > d2[j][i] + d2[i][k])
					d2[j][k] = d2[j][i] + d2[i][k];
			}
		}
	}
	double c1 = 0, c2 =0 ;
	for (int i = 1; i < tour.size(); i++)
	{
		int from = cities_num[tour[i-1]];
		int to = cities_num[tour[i]];
		c1 += d[from][to];
		c2 += d2[from][to];
	}
	if (c2 + r < c1)
		cout << "Yes";
	else
		cout << "No";
}