# ABC320-F Fuel Round Trip

https://atcoder.jp/contests/abc320/tasks/abc320_f

問題概要: 問題を読む

便宜上、座標$0$と座標$X_N$には$F = P = 0$のガソリンスタンドがあるとします。このようにしても最終的な解に影響は無いです。

往路のみの場合、[AOJ-2151](https://onlinejudge.u-aizu.ac.jp/problems/2151)のように、情報を増やした頂点上の最短経路問題を考えることで解けるので、往復の場合も同様にできないか考えてみます。

頂点の持つ情報を(現在の座標, 往路での現在の体力, 復路での現在の体力)としたグラフを考えます。ガソリンスタンドの料金を辺の重みとして座標$X_N$の頂点から座標$0$の頂点への最短経路問題を解きます。
- $(N + 1) \times (H + 1)$頂点

座標$i-i + 1$間の移動について考えてみます。$3$通りの移動方法(辺の張り方)が考えられます。
- 往路でも復路でもガソリンスタンドを利用しない
- 往路でガソリンスタンドを利用する
- 復路でガソリンスタンドを利用する

このうち、復路でガソリンスタンドを使うのがやっかいです。往路でガソリンスタンドを利用していないという制約があるからです。

これを解決するには、頂点の情報をさらに増やし(現在の座標, 往路でこの座標のガソリンスタンドを利用したか, 往路での現在の体力, 復路での現在の体力)とします。
- $(N + 1) \times 2 \times (H + 1)$

復路でガソリンスタンドを利用する移動は「往路でこの座標のガソリンスタンドを利用したか」がfalseである頂点からしかできない。

往路でガソリンスタンドを利用する移動は、辺の向かう先を「往路でこの座標のガソリンスタンドを利用したか」がtrueであるような頂点にしなければいけない。

の2点に注意します。あと、始点と終点にも気をつけます。

今回のグラフの最短経路の計算はdpでやれて、$O(NH^2)$で解けました

#include <bits/stdc++.h>


namespace zawa {

template <class T1, class T2>
bool Chmin(T1& fr, const T2& bk) {
    return fr > bk and (fr = bk, true);
}

} // namespace zawa
using namespace zawa;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, h; std::cin >> n >> h;
    std::vector<int> x(n + 1);
    for (int i{1} ; i <= n ; i++) std::cin >> x[i];
    std::vector<int> p(n + 1), f(n + 1);
    for (int i{1} ; i < n ; i++) std::cin >> p[i] >> f[i];

    std::vector useInv(n + 1, std::vector(h + 1, std::vector<int>{}));
    std::vector notUseInv{ useInv };
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j <= h ; j++) {
            int d{ x[i + 1] - x[i] };
            if (j - d >= 0) 
                notUseInv[i + 1][j - d].push_back(j);
            if (std::min(j + f[i], h) - d >= 0) 
                useInv[i + 1][std::min(j + f[i], h) - d].push_back(j);
        }
    }

    const long long sup{ (long long)4e18L };
    std::vector dp(2, std::vector(h + 1, std::vector<long long>(h + 1, sup)));
    for (int i{} ; i <= h ; i++) 
        dp[false][i][i] = 0;

    for (int i{n} ; i > 0 ; i--) {
        std::vector nxt(2, std::vector(h + 1, std::vector<long long>(h + 1, sup)));
        const int d{ x[i] - x[i - 1] };
        for (int j{} ; j <= h ; j++) {
            for (int k{} ; k <= h ; k++) {
                // not use both
                if (j - d >= 0) for (auto v : notUseInv[i][k]) {
                    Chmin(nxt[false][j - d][v], dp[false][j][k]);
                    Chmin(nxt[false][j - d][v], dp[true][j][k]);
                }
                // use only outward
                if (j - d >= 0) for (auto v : useInv[i][k]) {
                    Chmin(nxt[true][j - d][v], dp[false][j][k] + p[i - 1]);
                    Chmin(nxt[true][j - d][v], dp[true][j][k] + p[i - 1]);
                }
                int useK{ std::min(j + f[i], h) };
                // use only return
                if (useK - d >= 0) for (auto v : notUseInv[i][k]) {
                    Chmin(nxt[false][useK - d][v], dp[false][j][k] + p[i]);
                }
                // use both
                if (useK - d >= 0) for (auto v : useInv[i][k]) {
                    Chmin(nxt[true][useK - d][v], dp[false][j][k] + p[i] + p[i - 1]);
                }
            }
        }
        dp = std::move(nxt);
    }
    long long ans{ sup };
    for (int i{} ; i < 2 ; i++) for (int j{} ; j <= h ; j++) {
        Chmin(ans, dp[i][j][h]);
    }
    std::cout << (ans == sup ? -1LL : ans) << std::endl;
}

## 感想

往路と復路を同時にこなすというアイデアを思いつくのが難しかった。座標$i-i + 1$間の往復の移動だけで座標$i$のガソリンスタンドの利用状況を把握できるという構造を見抜くのに苦戦したのが原因だと思う。問題をもっと睨みます。

## update

2023/10/18: 「DAG上の最短経路はすべてdpでできる」と解釈されそうな表現があったので修正。左は嘘([参考](https://kmyk.github.io/blog/blog/2019/09/19/dp-is-not-shortest-path-of-dag/))