啊 这是网络流24T中的一题，可是那玩意儿我没学
那就DP吧
状态转移方程很容易得到
但这道题并不是往前走就完事儿了，即这道题的状态转移是有后效性的，不能用普通的循环来DP。
即这道题的状态转化成一个图以后，不是拓扑图。
这时候就需要用最短路算法来DP（其实DP都可以用图论的算法来处理，不过因为通常是拓扑图，所以可以直接循环DP）
个人认为书上用Dijkstra算法的正确性是不能保证的，因为这道题里某个点即使是在出对之后，也有可能被其他点更新 ，而DJ算法的核心正是每个点只会出队一次，正确性自然得不到保证。
但是SPFA算法就没有这个顾虑，直接TM SPFA。
#include<bits/stdc++.h> using namespace std; const int N=105; int Map[N][N]; bool vis[N][N][15]; int n,k,a,b,c; int dis[N][N][15]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct node{ int x,y,step; }edge[N*N*15]; int main() { 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",&Map[i][j]); memset(dis,0x3f,sizeof(dis)); dis[1][1][k]=0;vis[1][1][k]=1; queue<node> Q; Q.push((node){1,1,k}); while(!Q.empty()) { node tmp=Q.front();Q.pop(); int x=tmp.x,y=tmp.y,step=tmp.step; vis[x][y][step]=0; if(Map[x][y]&&step!=k) { if(dis[x][y][k]>dis[x][y][step]+a) { dis[x][y][k]=dis[x][y][step]+a; if(!vis[x][y][k]) vis[x][y][k]=1,Q.push((node){x,y,k}); } continue; //要是这个点可以加油，它就一定要加油（见题目），就不能更新其他状态，直接continue } if(step!=k&&dis[x][y][k]>dis[x][y][step]+a+c) { dis[x][y][k]=dis[x][y][step]+a+c; if(!vis[x][y][k]) vis[x][y][k]=1,Q.push((node){x,y,k}); } if(step>0) for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>n) continue; int Cost=((nx<x)||(ny<y)) ? b : 0; if(dis[nx][ny][step-1]>dis[x][y][step]+Cost) { dis[nx][ny][step-1]=dis[x][y][step]+Cost; if(!vis[nx][ny][step-1]) vis[nx][ny][step-1]=1,Q.push((node){nx,ny,step-1}); } } } int res=0x3f3f3f3f; for(int i=0;i<=k;i++) res=min(res,dis[n][n][i]); cout<<res; return 0; }