글 읽기 - 갱신이 안되는 루트가 있는데 왜 그런지 모르겠습니다.

yomyom0824 5년 전 0

갱신이 안되는 루트가 있는데 왜 그런지 모르겠습니다.

풀이는 플로이드 알고리즘으로 풀었습니다.ㅠㅠ

부디 알려주세용..

#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <regex>
#include <sstream>
#include <utility>
#include <list>
#define endl	'\n'
#define MOD 1000000
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
int dx[] = { 1,-1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,1,-1 };
const int INF = 1000000;
int dist_y[101][101];
int dist_n[101][101];
int n, ticket, m;
map<string, int> mp;

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


	cin >> n >> ticket;

	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++) {
			dist_n[i][j] = (i == j ? 0 : INF);
			dist_y[i][j] = (i == j ? 0 : INF);
		}


	string t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		mp.insert({ t,i });
	}

	vector<int> seq;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> t;
		seq.push_back(mp[t]);
	}

	int a;
	cin >> a;
	for (int i = 0; i < a; i++) {
		string type, s, e;
		int cost;
		cin >> type >> s >> e >> cost;
		int start = mp[s], end = mp[e];
		dist_n[start][end] = min(dist_n[start][end], cost);
		// 무궁화 새마을 청춘 -> 무료 / s v train 50 할인 / 나머지 그대로
		if (type == "ITX-Cheongchun" || type == "Mugunghwa" || type == "ITX-Saemaeul") dist_y[start][end] = 0;
		else if (type == "S-Train" || type == "V-Train") dist_y[start][end] = min(dist_y[start][end],(cost >> 1));
		else dist_y[start][end] = min(dist_y[start][end], cost);
	}

	


	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist_n[i][j] = min(dist_n[i][j], dist_n[i][k] + dist_n[k][j]);
				dist_y[i][j] = min(dist_y[i][j], dist_y[i][k] + dist_y[k][j]);
			}
		}
	}






	int total_y = ticket, total_n = 0;
	for (int i = 0; i < seq.size() - 1; i++) {
		total_y += dist_y[seq[i]][seq[i + 1]];
		total_n += dist_n[seq[i]][seq[i + 1]];
	}

	if (total_y >= total_n) cout << "No";
	else cout << "Yes";

	return 0;
}

yomyom0824 5년 전 0

" 한국에는 두 도시 사이를 오갈 수 있는 K개의 교통수단이 있습니다. "

한 방향으로만 갈 수 있는 줄 알았습니다.. 문제를 잘 읽어야겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

갱신이 안되는 루트가 있는데 왜 그런지 모르겠습니다.

yomyom0824 5년 전 0

yomyom0824 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말