티스토리 뷰

알고리즘 관련/BOJ

BOJ)13168 내일로 여행

JASON 자손9319 2016. 12. 30. 17:09

문제: icpc.me/13168


최단 거리로 각각의 도시들을 순서대로 여행 다닐 때 내일로 티켓을 구매할지 안할지 결정해 주면 된다.


내일로 티켓을 구매 했을 경우와 구매하지 않았을 경우에 대하여 각각 그래프를 만들어 준 후 n이 100밖에 안되니 플로이드 워셜을 돌려주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#define INF 987654321
using namespace std;
int n, r, x, y;
string a, b, c;
map<stringint> mp;
vector<int> trip;
int arr[110][110];
int brr[110][110];
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)arr[i][j] = brr[i][j] = 0;
            else arr[i][j] = brr[i][j] = INF;
        }
    }
}
void fw() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][k] + arr[k][j] < arr[i][j])
                    arr[i][j] = arr[i][k] + arr[k][j];
                if (brr[i][k] + brr[k][j] < brr[i][j])
                    brr[i][j] = brr[i][k] + brr[k][j];
            }
        }
    }
}
bool sol() {
    int ac = 0, bc = 0;
    for (int i = 0; i < trip.size() - 1; i++) {
        ac += arr[trip[i]][trip[i + 1]];
        bc += brr[trip[i]][trip[i + 1]];
    }
    return bc + r < ac;
}
int main()
{
    scanf("%d%d"&n, &r);
    init();
    for (int i = 1; i <= n; i++) {
        cin >> a;
        mp[a] = i;
    }
    scanf("%d"&x);
    for (int i = 0; i < x; i++) {
        cin >> a;
        trip.push_back(mp[a]);
    }
    scanf("%d"&x);
    for (int i = 0; i < x; i++) {
        cin >> a >> b >> c;
        scanf("%d"&y);
        arr[mp[b]][mp[c]] = min(y, arr[mp[b]][mp[c]]);
        arr[mp[c]][mp[b]] = min(y, arr[mp[b]][mp[c]]);
        if (a == "S-Train" || a == "V-Train") {
            brr[mp[b]][mp[c]] = min(y / 2, brr[mp[b]][mp[c]]);
            brr[mp[c]][mp[b]] = min(y / 2, brr[mp[b]][mp[c]]);
        }
        else if(a=="Mugunghwa"||a=="ITX-Saemaeul"||a=="ITX-Cheongchun") {
            brr[mp[b]][mp[c]] = 0;
            brr[mp[c]][mp[b]] = 0;
        }
        else {
            brr[mp[b]][mp[c]] = min(y, brr[mp[b]][mp[c]]);
            brr[mp[c]][mp[b]] = min(y, brr[mp[b]][mp[c]]);
        }
    }
    fw();
    printf("%s\n", sol() ? "Yes" : "No");
    return 0;
}
cs



'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11895 속이기  (0) 2017.01.03
BOJ)2401 최대 문자열 붙여넣기  (1) 2016.12.30
BOJ)13168 내일로 여행  (0) 2016.12.30
BOJ)13911 집 구하기  (0) 2016.12.30
BOJ 5719) 거의 최단 경로  (12) 2016.12.29
BOJ 7894) 큰 숫자  (0) 2016.12.29
댓글
댓글쓰기 폼