题意：给定一个 N×N的方形网格，设其左上角为起点，坐标为 (1,1)，X轴向右为正， Y 轴向下为正，每个方格边长为 1 。 一辆汽车从起点出发驶向右下角终点 (N,N) 。 在若干个网格交叉点处，设置了油库。汽车在行驶过程中应遵守如下规则：汽车只能沿网格边行驶，装满油后能行驶 K 条网格边；出发时汽车已装满油，在起点与终点处不设油库； 汽车经过一条网格边时，若其X 坐标或 Y 坐标减小，则应付费用 B ，否则免付费用； 汽车在行驶过程中遇油库则应加满油并付加油费用 A；在需要时可在网格点处增设油库，并付增设油库费用 C (不含加油费用 A )。 求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

 

设计好状态直接跑Dijkstra最短路即可。

#include
     
      using namespace std;const int N=110;const int INF=0x3f3f3f3f;const int dx[]={-1,0,1,0};const int dy[]={
   0,1,0,-1};int n,k,A,B,C,mp[N][N];struct node{    int x,y,k;    int d;    node() {}    node(int x,int y,int k,int d) : x(x),y(y),k(k),d(d) {}    bool operator < (const node &rhs) const {        return d>rhs.d;    }};int d[N][N][15]; bool vis[N][N][15];priority_queue
      
        q; int Dijkstra() {    memset(d,0x3f,sizeof(d));    memset(vis,0,sizeof(vis));    d[1][1][k]=0; q.push(node(1,1,k,0));    int ret=INF;    while (!q.empty()) {        node u=q.top(); q.pop();        if (u.x==n && u.y==n) ret=min(ret,u.d);        if (vis[u.x][u.y][u.k]) continue;        vis[u.x][u.y][u.k]=1;                for (int i=0;i<4;i++) {  //走路             int nx=u.x+dx[i],ny=u.y+dy[i],nk=u.k-1;            if (nx<1 || nx>n || ny<1 || ny>n || nk<0) continue;            int tmp=d[u.x][u.y][u.k];            if (nx
       
        >n>>k>>A>>B>>C;    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&mp[i][j]);            cout<
        
         <