13168번: 내일로 여행

https://www.acmicpc.net/problem/13168

내일로 티켓을 사용했을 때와 사용하지 않았을 때의 도시간 이동하는데 드는 최소 비용을 플로이드 알고리즘으로 구한다. 두 계획에 대해 각각 여행에 드는 비용을 계산하고 비교한다.

시간복잡도는 $O(k\lg n +n^3)$

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
int n, m, r, k, cost[10000], dp[100][100], c;
string plan[200], t, type[10000], s[10000], e[10000];
map<string, int> city;
int main() {
    cin >> n >> r; r <<= 1;
    fill(dp[0], dp[n], 1e9);
    for (int i = 0; i < n; i++) {
        cin >> t;
        city[t] = i;
        dp[i][i] = 0;
    }
    cin >> m;
    for (int i = 0; i < m; i++) cin >> plan[i];
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> type[i] >> s[i] >> e[i] >> cost[i]; cost[i] <<= 1;
        dp[city[e[i]]][city[s[i]]] = dp[city[s[i]]][city[e[i]]] = min(dp[city[s[i]]][city[e[i]]], cost[i]);
    }
    for (int x = 0; x < n; x++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][x] + dp[x][j]);
    for (int i = 1; i < m; i++) c += dp[city[plan[i - 1]]][city[plan[i]]];
    for (int i = 0; i < k; i++) {
        if (type[i][1] == '-') cost[i] /= 2;
        if (type[i].size() > 8) cost[i] = 0;
        dp[city[e[i]]][city[s[i]]] = dp[city[s[i]]][city[e[i]]] = min(dp[city[s[i]]][city[e[i]]], cost[i]);
    }
    for (int x = 0; x < n; x++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][x] + dp[x][j]);
    for (int i = 1; i < m; i++) r += dp[city[plan[i - 1]]][city[plan[i]]];
    puts(c > r ? "Yes" : "No");
    return 0;
}