汽车加油行驶

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2173 字
分层图Dijkstra，状态含剩余油量
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1502
// 题意：N*N 网格，车从 (1,1) 到 (N,N)，满油可走 K 条边，逆向行驶付费 B，遇油库必须加满油付费 A，无油库处可自建油库付费 C+A，求最小费用。
// 思路：以「所在格 + 剩余油量」为状态建分层图跑 Dijkstra，每个状态可以原地加油（或建库加油）把油量补满，也可以走一步消耗一格油。
// 复杂度：O(N^2*K*log(N^2*K)) 时间 / O(N^2*K) 空间
// 易错点：剩余油量为 0 时不能继续行走只能加油；原地建库的花费是 C+A 而不是只算 C，起点与终点不设油库。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 101;
const int MAXK = 11;
const int INF = 0x3f3f3f3f;
int dista[MAXN][MAXN][MAXK];
int oil[MAXN][MAXN];
int main(){
    int n, k, a, b, c;
    if(!(cin >> n >> k >> a >> b >> c)) return 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) cin >> oil[i][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int t = 0; t <= k; t++) dista[i][j][t] = INF;
        }
    }
    dista[1][1][k] = 0;
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;
    pq.push({0, 1, 1, k});
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    while(!pq.empty()){
        int du = get<0>(pq.top());
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        int f = get<3>(pq.top());
        pq.pop();
        if(du != dista[x][y][f]) continue;
        if(oil[x][y]){
            if(du + a < dista[x][y][k]){
                dista[x][y][k] = du + a;
                pq.push({dista[x][y][k], x, y, k});
            }
        }else{
            if(du + c + a < dista[x][y][k]){
                dista[x][y][k] = du + c + a;
                pq.push({dista[x][y][k], x, y, k});
            }
        }
        if(f == 0) continue;
        for(int t = 0; t < 4; t++){
            int nx = x + dx[t];
            int ny = y + dy[t];
            if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
            int nd = du;
            if(nx < x || ny < y) nd += b;
            if(nd < dista[nx][ny][f - 1]){
                dista[nx][ny][f - 1] = nd;
                pq.push({nd, nx, ny, f - 1});
            }
        }
    }
    int ans = INF;
    for(int t = 0; t <= k; t++){
        if(dista[n][n][t] < ans) ans = dista[n][n][t];
    }
    cout << ans << '\n';
    return 0;
}
汽车加油行驶

正文

一本通·提高篇的其它内容
