BOJ)13168 내일로 여행

문제: icpc.me/13168

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

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

#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<string, int> 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;
}