백준 13168번 내일로 여행



사용한 알고리즘 : 플로이드 와샬

문제를 제가 잘못 읽은건지... 여행 경로를 정해 준다는 조건을 몰라 초반에 많이 해맸습니다.

우선 map을 사용하여 도시의 이름들을 그냥 숫자로 생각했습니다. (map[도시이름] = 숫자)

N개의 도시 중 M개를 여행하는 경로가 주어집니다.

먼저 M개 경로를 LLL이라는 벡터에 저장해 주었습니다.

dist , railo 두 행렬을 만들어,

플로이드 와샬 3중 for구문을 돌릴때,

dist, railo 두 값을 따로 계산해 주었습니다.

이후 LLL벡터에 저장된 경로를 따라가며 경로에 따른 dist, railo 값들의 sum을 계산 후,

dist 값들의 합 vs railo값들의 합+R(내일로 구입비용) 을 비교해주면 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 987654321;
	int N, R, M, K;
	string name;
	map<string, int> town;
	vector<int> LLL;
	string Free[3] = {"Mugunghwa", "ITX-Saemaeul", "ITX-Cheongchun"};
	string Half[2] = {"S-Train", "V-Train"};
	int dist[300][300];
	int railo[300][300];
	long long Dis, Rail;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> R;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	if(i!=j){
	dist[i][j] = INF;
	railo[i][j] = INF;
	}
	}
	}
	for (int i = 0; i < N; ++i){
	cin >> name;
	town[name] = i;
	}
	cin >> M;
	for (int i = 0; i < M; ++i){
	cin >> name;
	LLL.push_back(town[name]);
	}
	cin >> K;
	for (int i = 0; i < K; ++i){
	bool free = false;
	bool half = false;
	string trans, n1, n2;
	int from, to, cost;
	cin >> trans >> n1 >> n2 >> cost;
	from = town[n1];
	to = town[n2];
	dist[from][to] = min(dist[from][to], cost);
	dist[to][from] = min(dist[to][from], cost);
	for (int i = 0; i < 3; ++i) if(trans == Free[i]) free=true;
	for (int i = 0; i < 2; ++i) if(trans == Half[i]) half=true;
	if(free) {
	railo[from][to] = 0;
	railo[to][from] = 0;
	}
	else if(half){
	railo[from][to] = min(railo[from][to], cost/2);
	railo[to][from] = min(railo[to][from], cost/2);
	}
	else{
	railo[from][to] = min(railo[from][to], cost);
	railo[to][from] = min(railo[to][from], cost);
	}
	}
	for (int k = 0; k < N; ++k){
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	railo[i][j] = min(railo[i][j], railo[i][k] + railo[k][j]);
	}
	}
	}
	for (int i = 0; i < M-1; ++i){
	int from = LLL[i];
	int to = LLL[i+1];
	Dis += dist[from][to];
	Rail += railo[from][to];
	}
	if(Dis > Rail+R) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return 0;
	}

view raw BOJ 13168.cpp hosted with ❤ by GitHub