問題概要

100 階建ての 2 つの建物 A, B がある。

A, B 内では 1 フロア上下するのに $Y$ 秒を要する
A の $i$ 階と B の $i$ 階とが廊下でつながっていて、移動に $X$ 秒を要する
A の $i+1$ 階と B の $i$ 階とが廊下でつながっていて、移動に $Y$ 秒を要する

建物 A の $a$ 階から建物 B の $b$ 階へ移動するのに要する最小時間を求めよ。

解法 (1)：算数

ややこしいのが、同一建物内での上下移動をするよりも、廊下の移動を繰り返すのがよい場合がある。

しかしながら、廊下の使用回数が中途半端になるケースは考えなくて大丈夫。よって、以下のいずれかの場合のみ考えれば OK。

最初に B の $a$ 階へと移動して、B 内での上下移動で到達する場合
最初に B の $a-1$ 階へと移動して、B 内での上下移動で到達する場合
廊下移動のみで到達する場合
- $a \gt b$ のとき、 $2(a-b)-1$ 回の廊下移動で到達できる
- $a \le b$ のとき、 $2(b-a)+1$ 回の廊下移動で到達できる

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long A, B, X, Y;
    cin >> A >> B >> X >> Y;
    --A, --B;
    long long res = X + Y * abs(B-A);
    if (A > 0) chmin(res, X + Y * abs(B-(A-1)));
    if (A > B) chmin(res, X * ((A-B)*2-1));
    else chmin(res, X * ((B-A)*2+1));
    cout << res << endl;
}

解法 (2)：Floyd--Warshall 法

場合分けが怖かったので Dijkstra 法をしたのだけど、Floyd--Warshall 法の方が早いね。 $V = 200$ として $O(V^{3})$ なので十分間に合う。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
int main() {
    long long A, B, X, Y;
    cin >> A >> B >> X >> Y;
    --A, --B;
    vector<vector<long long>> dp(200, vector<long long>(200, INF));
    for (int u = 0; u < 100; ++u) {
        if (u != 99) {
            dp[u][u+1] = dp[u+1][u] = Y;
            dp[u+100][u+101] = dp[u+101][u+100] = Y;
        }
        dp[u][u+100] = dp[u+100][u] = X;
        if (u > 0) dp[u][u+99] = dp[u+99][u] = X;
        dp[u][u] = 0;
    }
    for (int k = 0; k < 200; ++k)
        for (int i = 0; i < 200; ++i) 
            for (int j = 0; j < 200; ++j)
                chmin(dp[i][j], dp[i][k] + dp[k][j]);
    cout << dp[A][B+100] << endl;
}