백준 - 내일로 여행 (13168)

1. 문제 링크

내일로 여행

2. 풀이

플로이드 와샬로 각 도시 사이를 이동할 수 있는 최소 비용을 초기화하고,
여행하려는 도시를 순서대로 방문하며 비용을 누적하면 됩니다.

3. 전체 코드

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

const double INF = 1000001.0;
int n, r, m, k;
int travel[205];
double d[2][105][105];
unordered_map<string, int> city;

double mmin(double a, double b) {
	return a < b ? a : b;
}

void init(int idx) {
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[idx][i][j] = min(d[idx][i][j], d[idx][i][k] + d[idx][k][j]);
			}
		}
	}
}

double solve(int idx) {
	double ret = 0;

	for (int i = 0; i < m - 1; i++) {
		ret += d[idx][travel[i]][travel[i + 1]];
	}

	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> r;

	memset(d, INF, sizeof(d));

	for (int i = 0; i < n; i++) {
		string name; cin >> name;
		city[name] = i;
		d[0][i][i] = d[1][i][i] = 0;
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		string name; cin >> name;
		travel[i] = city[name];
	}

	cin >> k;

	while (k--) {
		string train, a, b;
		double cost;
		cin >> train >> a >> b >> cost;

		d[0][city[a]][city[b]] = mmin(d[0][city[a]][city[b]], cost);
		d[0][city[b]][city[a]] = mmin(d[0][city[b]][city[a]], cost);

		if (train == "S-Train" || train == "V-Train") {
			d[1][city[a]][city[b]] = mmin(d[1][city[a]][city[b]], cost / 2);
			d[1][city[b]][city[a]] = mmin(d[1][city[b]][city[a]], cost / 2);
		}
		else if (train == "Mugunghwa" || train == "ITX-Saemaeul" || train == "ITX-Cheongchun") {
			d[1][city[a]][city[b]] = 0;
			d[1][city[b]][city[a]] = 0;
		}
		else {
			d[1][city[a]][city[b]] = mmin(d[1][city[a]][city[b]], cost);
			d[1][city[b]][city[a]] = mmin(d[1][city[b]][city[a]], cost);
		}
	}

	init(0);
	init(1);
	cout << solve(0) << ' ' << solve(1) << '\n';
	cout << (solve(0) > solve(1) + r ? "Yes" : "No");

	return 0;
}

자꾸 100%에서 틀려서 "맞왜틀!!" 외치는 중에,
질문 검색을 보니 비용을 double로 선언해야 한다고 합니다...
그래서 double로 해도 자꾸 틀려서 왜 그런가... 보니까
INF가 너무 커서 overflow가 발생하고 있었습니다.

그래서 이렇게 시간을 날려먹었습니다...
ps하다가 이럴 때 진짜 현타오고 관두고 싶네요;
타입 신경 안 쓰는 자바스크립트가 역시 짱입니다.