「网络流 24 题」汽车加油行驶问题
题解：对于一个点如果是没有加油站，就有设置加油站或者是直接走，通过调整方向函数将向回走的放在前面，然后就可以收费。

#include <bits/stdc++.h>

const int MAXN = 105,INF = 10000000;
const int fx[] = {-1,0,1,0},fy[] = {0,-1,0,1};

using namespace std;

int n,k,a,b,c,ans;
int oil[MAXN][MAXN],dis[MAXN][MAXN][20];
bool inq[MAXN][MAXN][20];

inline void init()
{
    scanf("%d %d %d %d %d",&n,&k,&a,&b,&c);
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            scanf("%d",&oil[i][j]);
}

struct node{
    int x,y,Oil;
};

inline bool check(node car,int i){
    if(car.x + fx[i] < 1 || car.x + fx[i] >  n) return false;
    if(car.y + fy[i] < 1 || car.y + fy[i] >  n) return false;
    if(car.Oil == 0) return false;
    return true;
}

queue<node>Q;
inline void spfa()
{
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            for(int o = 0;o <= k;o++)
                dis[i][j][o] = INF;
    
    Q.push((node){1,1,k});dis[1][1][k] = 0;inq[1][1][k] = false;
    while(!Q.empty()){
        node car = Q.front();Q.pop();inq[car.x][car.y][car.Oil] = false;
        int ux = car.x,uy = car.y;
        for(int i = 0;i <= 3;i++){
            if(check(car,i)){
                int vx = ux + fx[i],vy = uy + fy[i];
                if(i <= 1){    //pay B
                    if(oil[vx][vy]) {//pay A
                        if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + b + a){
                            dis[vx][vy][k] = dis[ux][uy][car.Oil] + b + a;
                            if(!inq[vx][vy][k]){
                                Q.push((node){vx,vy,k});
                                inq[vx][vy][k] = true;
                            }
                        }
                    }
                    else {
                        if(dis[vx][vy][car.Oil-1] > dis[ux][uy][car.Oil] + b && !(vx != n && vy != n && car.Oil - 1 == 0)){
                            dis[vx][vy][car.Oil-1] = dis[ux][uy][car.Oil] + b;
                            if(!inq[vx][vy][car.Oil-1]){
                                Q.push((node){vx,vy,car.Oil-1});
                                inq[vx][vy][car.Oil-1] = true;
                            }
                        }
                        if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a + b + c){
                            dis[vx][vy][k] = dis[ux][uy][car.Oil] + a + b + c;
                            if(!inq[vx][vy][k]){
                                Q.push((node){vx,vy,k});
                                inq[vx][vy][k] = true;
                            }
                        }
                    }
                }
                else {
                    if(oil[vx][vy]) {
                        if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a){
                            dis[vx][vy][k] = dis[ux][uy][car.Oil] + a;
                            if(!inq[vx][vy][k]){
                                Q.push((node){vx,vy,k});
                                inq[vx][vy][k] = true;
                            }
                        }
                    }
                    else {
                        if(dis[vx][vy][car.Oil-1] > dis[ux][uy][car.Oil] && !(vx != n && vy != n && car.Oil - 1 == 0)){
                            dis[vx][vy][car.Oil-1] = dis[ux][uy][car.Oil];
                            if(!inq[vx][vy][car.Oil-1]){
                                Q.push((node){vx,vy,car.Oil-1});
                                inq[vx][vy][car.Oil-1] = true;
                            }
                        }
                        if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a + c){
                            dis[vx][vy][k] = dis[ux][uy][car.Oil] + a + c;
                            if(!inq[vx][vy][k]){
                                Q.push((node){vx,vy,k});
                                inq[vx][vy][k] = true;
                            }
                        }
                    }                    
                } 
            }
        }
    }
} 

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    spfa();
    ans = INF;
    for(int i = 0;i <= k;i++) ans = min(ans,dis[n][n][i]);
    printf("%d\n",ans);
    return 0;
}