13分dijkstra求调
查看原帖
13分dijkstra求调
750365
FarmarJohn楼主2024/3/2 11:37

rt,剩下的都RE了。

#include<bits/stdc++.h>
using namespace std;
const int N=10000010,M=50000010;
struct edge
{
	int to,dis,next;
}e[M];
int head[N],dis[N],n,m,s,cnt;
bool vis[N];
inline void add(const int u,const int v,const int w)
{
	++cnt;
	e[cnt].dis=w;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
	++cnt;
	e[cnt].dis=w;
	e[cnt].to=u;
	e[cnt].next=head[v];
	head[v]=cnt;
}
struct node
{
	int dis,pos;
	inline bool operator < (const node &x)const
	{
		return x.dis<dis;
	}
};
priority_queue<node>q;
inline void dijkstra()
{
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos;
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis)
			{
				dis[y]=dis[x]+e[i].dis;
				if(!vis[y])
				{
					q.push((node){dis[y],y});
				}
			}
		}
	}
}
bool vv[20005];
char tu[505][505];
int t;
inline int findA(const int N,const int M,const char A)
{
	for(int i=N;i<=n;++i)
	{
		for(int j=M;j<=m;++j)
		{
			if(tu[i][j]==A&&(i!=N&&j!=M))return (i-1)*m+j;
		}
	}
}
inline void chuan()
{
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(tu[i][j]>='A'&&tu[i][j]<='Z'&&!vv[tu[i][j]-'A'])
			{
				vv[tu[i][j]-'A']=1;
				add((i-1)*m+j,findA(i,j,tu[i][j]),0);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n*m;++i)dis[i]=0x7fffffff;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin >> tu[i][j];
			if(tu[i][j]=='@')s=(i-1)*m+j;
			if(tu[i][j]=='=')t=(i-1)*m+j;
		}
	}
	chuan();
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(tu[i][j]=='#')continue;
			if(tu[i+1][j]!='#'&&i+1<=n&&i+1>=1)add((i-1)*m+j,i*m+j,1);
			if(tu[i-1][j]!='#'&&i-1<=n&&i-1>=1)add((i-1)*m+j,(i-2)*m+j,1);
			if(tu[i][j+1]!='#'&&j+1<=n&&j+1>=1)add((i-1)*m+j,(i-1)*m+j+1,1);
			if(tu[i][j-1]!='#'&&j-1<=n&&j-1>=1)add((i-1)*m+j,(i-1)*m+j-1,1);
		}
	}
	dijkstra();
	cout << dis[t];
	return 0;
}
2024/3/2 11:37
加载中...