本文共 1755 字，大约阅读时间需要 5 分钟。
还是SPFA呀。。。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define MAX 120inline int read(){ int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}struct Line{ int v,next,w;}e[MAX*MAX*MAX];int h[MAX*MAX],cnt=1,tot;int m[MAX*MAX],g[MAX][MAX],n,K,A,B,C;bool vis[MAX*MAX][15];inline void Add(int u,int v,int w){ e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}int dis[MAX*MAX][15];void SPFA(){ memset(dis,63,sizeof(dis)); dis[g[1][1]][K]=0; queue Q,Q1; Q.push(g[1][1]);Q1.push(K); while(!Q.empty()) { int u=Q.front(),t=Q1.front(); Q.pop();Q1.pop(); if(t!=0) { for(int i=h[u];i;i=e[i].next) { int v=e[i].v,gg=t-1,Dis=dis[u][t]+e[i].w; if(m[v])gg=K,Dis+=A; if(dis[v][gg]>Dis) { dis[v][gg]=Dis; if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg); } } } int v=u,gg=K,Dis=dis[u][t]+C+A; if(dis[v][gg]>Dis) { dis[v][gg]=Dis; if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg); } vis[u][t]=false; }}int main(){ freopen("trav.in","r",stdin); freopen("trav.out","w",stdout); n=read();K=read();A=read();B=read();C=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) g[i][j]=++tot,m[g[i][j]]=read();; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(i!=n)Add(g[i][j],g[i+1][j],0); if(j!=n)Add(g[i][j],g[i][j+1],0); if(i!=1)Add(g[i][j],g[i-1][j],B); if(j!=1)Add(g[i][j],g[i][j-1],B); } SPFA(); int ans=1e9; for(int i=0;i<=K;++i)ans=min(ans,dis[g[n][n]][i]); printf("%d\n",ans); return 0;}
转载于:https://www.cnblogs.com/cjyyb/p/8193340.html