题面：
思路：
汽车油箱最多只能装10格油，因此可以依据油量建立分层图（共11层），然后spfa跑最短路
不用把每一条边都建出来，用的时候判断就好了
没了
真是披着网络流外衣的最短路啊
Code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define inf 1000000000 6 using namespace std; 7 inline int read(){ 8 int re=0,flag=1;char ch=getchar(); 9 while(ch>'9'||ch<'0'){ 10 if(ch=='-') flag=-1; 11 ch=getchar(); 12 } 13 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 14 return re*flag; 15 } 16 const int dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1}; 17 int n,m,k1,k2,k3,a[110][110]; 18 int dis[110][110][20];bool vis[110][110][20]; 19 struct que{ 20 int x,y,z; 21 que(){} 22 que(int xx,int yy,int zz){x=xx;y=yy;z=zz;} 23 }; 24 que q[1000010]; 25 void spfa(){ 26 int i,j,k,x,y,z,tx,ty,tz,tc,head=0,tail=1; 27 for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=0;k<=m;k++) dis[i][j][k]=inf; 28 q[0]=que(1,1,m);vis[1][1][m]=1;dis[1][1][m]=0; 29 while(head<tail){ 30 x=q[head].x;y=q[head].y;z=q[head++].z;vis[x][y][z]=0; 31 // cout<<"spfa "<<x<<ends<<y<<ends<<z<<ends<<dis[x][y][z]<<endl; 32 for(i=1;i<=4;i++){ 33 tx=x+dx[i];ty=y+dy[i]; 34 if(tx<1||tx>n||ty<1||ty>n) continue; 35 tz=(a[tx][ty]?m:(z-1));tc=dis[x][y][z]; 36 if(a[tx][ty]) tc+=k1; 37 if(i<=2) tc+=k2; 38 if(z==0) tz=(a[tx][ty]?m:(m-1)),tc+=k3+k1; 39 // cout<<" to "<<tx<<ends<<ty<<ends<<tz<<ends<<tc<<ends<<dis[tx][ty][tz]<<endl; 40 if(tc<dis[tx][ty][tz]){ 41 dis[tx][ty][tz]=tc; 42 if(!vis[tx][ty][tz]){ 43 q[tail++]=que(tx,ty,tz);vis[tx][ty][tz]=1; 44 } 45 } 46 } 47 } 48 } 49 int main(){ 50 freopen("trav.in","r",stdin); 51 freopen("trav.out","w",stdout); 52 int i,j,k,ans=inf; 53 n=read();m=read();k1=read();k2=read();k3=read(); 54 for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=read(); 55 spfa(); 56 // for(i=1;i<=n;i++){ 57 // for(j=1;j<=n;j++){ 58 // for(k=0;k<=m;k++) cout<<dis[i][j][k]<<ends; 59 // } 60 // cout<<endl; 61 // } 62 for(i=0;i<=m;i++) ans=min(ans,dis[n][n][i]); 63 printf("%d",ans); 64 }