分层图60pts求调
查看原帖
分层图60pts求调
912241
dream_on_screen楼主2023/8/11 10:48

不知道为什么就错了好几个点,查了一晚上也没查出来

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n,k,a_,b_,c_;
int n_;
int c[105][105];
vector<vector<int>> e,w;
inline int id(int i,int j,int k)
{
	return ((i-1)*n+j)+k*(n*n);
}
class graph
{
    template <class type>
    struct node
    {
        int id;
        type dis;
        bool operator < (node other) const
        {
            return this->dis>other.dis;
        }
    };
    public:
        const long long inf=0x3f3f3f3f;
        template <class type>
        type dij(int n,int l,vector<vector<type>>e,vector<vector<type>>w)
        {
            type dis[n+5];
            for(int i=1;i<=n;i++)
                dis[i]=inf;
            dis[l]=0;
            bool vis[n+5]={};
            priority_queue<node<type>>q;
            node<type>temp;
            temp.id=l;
            temp.dis=0;
            q.push(temp);
            while(q.size()!=0)
            {
                int t=q.top().id;
                q.pop();
                if(vis[t])
                    continue;
                vis[t]=true;
                for(int i=0;i<e[t].size();i++)
                {
                    int u=e[t][i];
                    if(dis[u]>dis[t]+w[t][i])
                    {
                        dis[u]=dis[t]+w[t][i];
                        node<type>next;
                        next.id=u;
                        next.dis=dis[u];
                        q.push(next);
                    }
                }
            }
            vector<type>ans;
            ans.push_back(0);
            for(int i=1;i<=n;i++)
                ans.push_back(dis[i]);
            int f=0x3f3f3f3f3f;
            for(int i=0;i<=k;i++)
            	f=min(f,dis[id(n_,n_,i)]);
            return f;
        }
};
template <class type>
type dij(int n,int l,vector<vector<type>>e,vector<vector<type>>w)
{
    graph g;
    return g.dij(n,l,e,w);
}
inline void to_id(int num,int &i,int &j,int &k)
{
	j=num%n;
	if(j==0)
		j=n;
	k=num/(n*n);
	if(num%(n*n)==0)
		k--;
	int id=num%(n*n);
	if(id==0)
		id=n*n;
	i=id/n+1;
	if(id%n==0)
		i--;
}
inline void add(int u,int v,int s)
{
	e[u].push_back(v);
	w[u].push_back(s);
}
inline bool safe(int x,int y)
{
	return x>=1&&x<=n&&y>=1&&y<=n;
}
int main()
{
	cin>>n>>k>>a_>>b_>>c_;
	e.resize(150005);
	w.resize(150005);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>c[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int l=0;l<=k;l++)//还剩l格油
			{
				int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
				for(int s=1;s<=4;s++)
					if(safe(i+dx[s],j+dy[s]))
					{
						//下一个位置
						int nx=i+dx[s],ny=j+dy[s];
						//记录费用
						int money=0;
						//加油站费用
						if(l==0&&c[i][j]==1)
						{
							money+=a_;
						}
						else
						{
							if(l==0)
								money+=c_+a_;
						}
						if(c[nx][ny]==1)
							money+=a_;
						if(s==2||s==4)
							money+=b_;
						int nl;//转移出来是哪一层
						if(l==0)
							nl=k;
						else if(c[nx][ny]==1)
							nl=k;
						else
							nl=l-1;
						add(id(i,j,l),id(nx,ny,nl),money);
					}
			}
	n_=n;
	cout<<dij(n*n+k*n*n,id(1,1,k),e,w);
	return 0;
}
2023/8/11 10:48
加载中...