思路与算法

以位置和剩余油量为状态。每走一条边消耗1油，向上或向左加费用B；进入已有油库必须付A并装满。无油库且不是起点的位置，可付A+C建站补满。初态在起点满油，Dijkstra求终点任意剩余油量的最小费用。费用未给位数上限，使用大整数。

正确性说明

状态记录以后合法行动和费用所需的全部即时信息。强制油库补满在进入时处理，新建站可用额外补油边表示，所有边费用非负，Dijkstra正确。虽然新建站在物理上可继续存在，但最优方案无需再次在已建站补油：两次补满后状态相同，可删去中间非负费用回路，甚至在第一次补满后直接接后续路线。因此不保存历史建站集合也能达到全局最优，且不会漏掉更优方案。

复杂度

O(N²K log(N²K)D)时间、O(N²KD)空间，D为累计费用位数；含网格、距离可达标记和优先队列初始化。

易错点

已有油库是必须加满并收费；起点和终点不设油库。油量0可以在当前位置建站再走，不能带0油走边。增加油库费用C不含加油A。坐标轴方向对应向左/向上收费。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};
struct State {
    cpp_int d;
    int id;
};
struct Greater {
    bool operator()(const State &a, const State &b) const {
        return a.d > b.d;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    cpp_int A, B, C;
    cin >> n >> K >> A >> B >> C;
    vector<int> station(n * n);
    for (int &x : station)
        cin >> x;
    int sz = n * n * (K + 1);
    vector<cpp_int> d(sz);
    vector<char> known(sz);
    auto id = [&](int p, int f) {
        return p * (K + 1) + f;
    };
    priority_queue<State, vector<State>, Greater> q;
    known[id(0, K)] = 1;
    q.push({0, id(0, K)});
    auto relax = [&](int v, cpp_int cost) {
        if (!known[v] || cost < d[v]) {
            known[v] = 1;
            d[v] = cost;
            q.push({cost, v});
        }
    };
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        if (cur.d != d[cur.id])
            continue;
        int p = cur.id / (K + 1), f = cur.id % (K + 1), x = p / n, y = p % n;
        if (p == n * n - 1) {
            cout << cur.d << "\n";
            return 0;
        }
        if (!station[p] && p && f < K)
            relax(id(p, K), cur.d + A + C);
        if (!f)
            continue;
        for (int dir = 0; dir < 4; dir++) {
            int xx = x + (dir == 0) - (dir == 1), yy = y + (dir == 2) - (dir == 3);
            if (xx < 0 || xx >= n || yy < 0 || yy >= n)
                continue;
            int v = xx * n + yy;
            cpp_int cost = cur.d;
            if (dir == 1 || dir == 3)
                cost += B;
            int nf = f - 1;
            if (station[v]) {
                nf = K;
                cost += A;
            }
            relax(id(v, nf), cost);
        }
    }
}