洛谷P4009 汽车加油行驶问题

@Pelom  November 9, 2019

题意

数据范围:$2 \le n \le 100,2 \le k \le 10$

题解

将油量视为状态,分层建图
之后跑最短路即可(也可跑费用流)

代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int N=200010;
const int INF=0x7fffffff;
struct edge{
    int nxt,to,w;
} e[N<<2];
int n,k,a,b,c,o;
int cnt,ans=INF;
int head[N],dis[N];
bool vis[N];
inline int min(int a,int b){
    return a<b?a:b;
}
inline void add(int ux,int uy,int uz,int vx,int vy,int vz,int w){
    int u=(uz-1)*n*n+(ux-1)*n+uy,v=(vz-1)*n*n+(vx-1)*n+vy;
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
inline void SPFA(){
    queue<int> Q;
    memset(dis,0x3f,sizeof(dis));
    Q.push(1);
    dis[1]=0;
    vis[1]=1;
    for(;!Q.empty();){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    Q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
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",&o);
            for(int p=1;p<=k;p++)
                add(i,j,p,i,j,p+1,0);
            if(o){
                for(int p=2;p<=k+1;p++)
                    add(i,j,p,i,j,1,a);
                if(i<n) 
                    add(i,j,1,i+1,j,2,0);
                if(j<n) 
                    add(i,j,1,i,j+1,2,0);
                if(i>1) 
                    add(i,j,1,i-1,j,2,b);
                if(j>1) 
                    add(i,j,1,i,j-1,2,b);
            }
            else{
                for(int p=1;p<=k;p++){
                    if(i<n) 
                        add(i,j,p,i+1,j,p+1,0);
                    if(j<n) 
                        add(i,j,p,i,j+1,p+1,0);
                    if(i>1) 
                        add(i,j,p,i-1,j,p+1,b);
                    if(j>1) 
                        add(i,j,p,i,j-1,p+1,b);
                }
                for(int p=2;p<=k+1;p++)
                    add(i,j,p,i,j,1,a+c);
            }
        }
    SPFA();
    for(int i=1;i<=k+1;i++)
        ans=min(ans,dis[n*n*i]);
    printf("%d",ans);
    return 0;
}

添加新评论