分层图最短路

把能够弹跳的曼哈顿距离看做能量

dp[i][j][k]表示在（i，j）位置，还有能量k的最少花费

弹跳的曼哈顿距离增加1，能量减1

当能量减为0时，花费费用充满能量

 

#include
     
      #include
      
       #include
       
         #define N 151 typedef long long LL; const LL inf=1e17; using namespace std; int n,m;int energy[N][N],cost[N][N]; int X[4],Y[4]; LL dp[N][N][N<<1];bool vis[N][N][N<<1]; int dx[5]={
   0,-1,0,1,0};int dy[5]={
   0,0,1,0,-1}; struct node{    int x,y,k;    LL val;         node(int x_=0,int y_=0,int k_=0,int val_=0) :x(x_),y(y_),k(k_),val(val_) {}         bool operator < (node p) const    {        return val>p.val;    }     }now; priority_queue
        
         q; void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;} void dijkstra(int e){    for(int i=1;i<=n;++i)        for(int j=1;j<=m;++j)            for(int k=0;k<=n+m-2;++k)            {                dp[i][j][k]=inf;                vis[i][j][k]=false;            }    while(!q.empty()) q.pop();    vis[X[e]][Y[e]][0]=true;    dp[X[e]][Y[e]][energy[X[e]][Y[e]]]=cost[X[e]][Y[e]];    now.x=X[e];    now.y=Y[e];    now.k=energy[now.x][now.y];    now.val=cost[now.x][now.y];    q.push(now);    int sx,sy,nx,ny,k;    while(!q.empty() && (!vis[X[1]][Y[1]][0] || !vis[X[2]][Y[2]][0] || !vis[X[3]][Y[3]][0]))    {        now=q.top();        q.pop();        sx=now.x; sy=now.y; k=now.k;        if(vis[sx][sy][k]) continue;        vis[sx][sy][k]=true;        if(now.k)        {               for(int i=0;i<5;++i)            {                nx=now.x+dx[i];                ny=now.y+dy[i];                if(nx<=0 || nx>n || ny<=0 || ny>m) continue;                if(dp[sx][sy][k]
         
          =inf) printf("NO");    else printf("%c\n%lld",pos,ans);    return 0;}