---

 

喜闻乐见的分层图最短路，注意到了加油站是强制要加满油的

---

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 110 10 #define SIZE 1000000 11 #define llg long long 12 #define inf (llg)1e16 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 15 llg n,m,k,A,B,C,dis[maxn*maxn][15],bj[maxn*maxn][maxn],se[maxn*maxn],head,tail; 16 llg p[5][4]; 17 vector
            
             a[maxn*maxn],val[maxn*maxn]; 18 19 llg num(llg x,llg y){ return (x-1)*n+y;} 20 21 void link(llg x,llg y,llg z){a[x].push_back(y),val[x].push_back(z);} 22 23 struct node 24 { 25 llg x,y; 26 }dl[SIZE+5]; 27 28 void init() 29 { 30 p[1][0]=1,p[2][1]=1,p[3][0]=-1,p[4][1]=-1; 31 cin>>n>>k>>A>>B>>C; 32 for (llg i=1;i<=n*n;i++) scanf("%lld",&se[i]); 33 for (llg i=1;i<=n;i++) 34 for (llg j=1;j<=n;j++) 35 for (llg w=1;w<=4;w++) 36 { 37 llg x=i+p[w][0],y=j+p[w][1]; 38 if (x>n || x<1 || y>n || y<1) continue; 39 if (w<=2) link(num(i,j),num(x,y),0); 40 else link(num(i,j),num(x,y),B); 41 } 42 for (llg i=1;i<=n*n;i++) for (llg j=0;j<=k;j++) dis[i][j]=inf; 43 tail=1,head=0; 44 dl[1].x=1;dl[1].y=k; dis[1][k]=0; 45 } 46 47 void spfa() 48 { 49 llg x,v,y,w; 50 do 51 { 52 head%=SIZE; head++; 53 x=dl[head].x,y=dl[head].y; 54 w=a[x].size(); bj[x][y]=0; 55 if (se[x] && y!=k) 56 { 57 if (dis[x][y]+A
             
              dis[x][y]+val[x][i]) 75 { 76 dis[v][y-1]=dis[x][y]+val[x][i]; 77 if (!bj[v][y-1]) 78 { 79 bj[v][y-1]=1; 80 tail%=SIZE; tail++; 81 dl[tail].x=v;dl[tail].y=y-1; 82 } 83 } 84 } 85 } 86 if (y!=k && se[x]==0) 87 { 88 if (dis[x][k]>dis[x][y]+C+A) 89 { 90 dis[x][k]=dis[x][y]+C+A; 91 if (!bj[x][k]) 92 { 93 bj[x][k]=1; 94 tail%=SIZE; tail++; 95 dl[tail].x=x,dl[tail].y=k; 96 } 97 } 98 } 99 }while(head!=tail);100 }101 102 int main()103 {104 yyj("car");105 init();106 // k--;107 spfa();108 llg ans=inf;109 for (llg i=0;i<=k;i++) ans=min(ans,dis[n*n][i]);110 cout<