dij38pts求调
查看原帖
dij38pts求调
785917
Chthollian楼主2024/9/12 14:51
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,cnt,last[90005],vis[90005],dis[90005];
vector<int> cs[30];
struct Edge
{
	int to,pre,val;
} edge[360005];
void add(int u,int v,int val)
{
	edge[++cnt].to=v;
	edge[cnt].pre=last[u];
	last[u]=cnt;
	edge[cnt].val=val;
}
char mp[305][305];
int xx[5]={0,1,-1,0,0};
int yy[5]={0,0,0,1,-1};
int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]>='A' && mp[i][j]<='Z')
			{
				cs[mp[i][j]-'A'].emplace_back((i-1)*m+j);
			}
			else if(mp[i][j]=='@')
			{
				s=(i-1)*m+j;
			}
			else if(mp[i][j]=='=')
			{
				t=(i-1)*m+j;
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='#')
			{
				continue;
			}
			if(mp[i][j]>='A' && mp[i][j]<='Z')
			{
				for(int t:cs[mp[i][j]-'A'])
				{
					if(t!=(i-1)*m+j)
					{
						add((i-1)*m+j,t,0);
						break;
					}
				}
			}
			for(int k=1;k<=4;k++)
			{
				int nx=i+xx[k],ny=j+yy[k];
				if(mp[nx][ny]=='@' || mp[nx][ny]=='=' || mp[nx][ny]=='.' || (mp[nx][ny]>='A' && mp[nx][ny]<='Z'))
				{
					add((i-1)*m+j,(nx-1)*m+ny,1);
				}
			}
		}
	}
	for(int i=1; i<=n*m; i++)
	{
		dis[i]=0x3f3f3f3f;
	}
	//cout<<cnt<<"\n";
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	dis[s]=0;
	q.emplace(make_pair(0,s));
	while(q.size())
	{
		int now=q.top().second;
		q.pop();
		if(!vis[now])
		{
			//cout<<now<<"\n";
			vis[now]=1;
			for(int i=last[now]; i; i=edge[i].pre)
			{
				int to=edge[i].to;
				if(dis[to]>dis[now]+edge[i].val)
				{
					dis[to]=dis[now]+edge[i].val;
					q.emplace(make_pair(dis[to],to));
				}
			}
		}
	}
	cout<<dis[t];
	return 0;
}
2024/9/12 14:51
加载中...