当前位置: 首页 > >

CCF 201409-4最优配餐

发布时间:


最优配餐

题目链接


题解

多源bfs求网格最短路
题意稍微解释一下,在上图中,在不经过红点的限定下,求绿点到最*的蓝点的距离,再对距离加权、求和,为最终的答案。对于多源最短路问题,一般的解法是建立一个超级源点,将问题化为单源最短路问题,再套一个spfa或者迪杰斯特拉算法即可。但是,对于网格问题的最短路,只需要考虑使用bfs即可解决,因为网格边权都是1,一层一层搜肯定是最短的,为了不重复搜,需要标记一下,最终复杂度相当于对这个网格图搜一遍,所以O(n^2) 1e6完全没问题。


代码

#include
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define maxn 1005
#define maxm 800000
#define INF 2000000005
#define ll long long

struct node{
int x,y,cnt;
};

bool vis[maxn][maxn];
bool ff[maxn][maxn];
int dis[maxn][maxn];
vector >st;
vectored;

int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
void bfs(int n)
{
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dis[i][j]=INF;

queue >Q;
for(int i=0;i {
dis[st[i].first][st[i].second]=0;
vis[st[i].first][st[i].second]=true;
Q.push(st[i]);
}

while(!Q.empty())
{
pairu=Q.front();
Q.pop();

for(int i=0;i<4;i++)
{
int nx=xx[i]+u.first;
int ny=yy[i]+u.second;
if(nx>0&&nx<=n&&ny>0&&ny<=n&&ff[nx][ny]==false&&vis[nx][ny]==false)
{
vis[nx][ny]=true;
dis[nx][ny]=dis[u.first][u.second]+1;
Q.push(make_pair(nx,ny));
}
}
}
}

int main()
{
IOS;
int n,m,k,d;
cin>>n>>m>>k>>d;

for(int i=0;i {
int x,y;
cin>>x>>y;
st.push_back(make_pair(x,y));
}

for(int i=0;i {
int x,y,z;
cin>>x>>y>>z;
ed.push_back(node{x,y,z});
}

for(int i=0;i {
int x,y;
cin>>x>>y;
ff[x][y]=true;
}

bfs(n);

ll ans=0;
for(int i=0;i {
ans+=dis[ed[i].x][ed[i].y]*ed[i].cnt;
}
cout< return 0;
}



友情链接: