堆优化Dijkstra TLE两个点,求大佬优化
查看原帖
堆优化Dijkstra TLE两个点,求大佬优化
203102
Diamiko楼主2021/10/6 18:16

自己感觉没什么问题,T三个点,加了一堆卡常T两个了

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int head,dis;
}node[251005];
struct Edge
{
	int next,to,len;
}edge[1000005];
int n,m,cnt,tot;
char c[503][503];
int ord[503][503];
inline void addEdge(int u,int v,int w)
{
	edge[++cnt]={node[u].head,v,w};
	node[u].head=cnt;
}
inline void Dijkstra()
{
	typedef pair<int,int> pii;
	priority_queue<pii,vector<pii>,greater<pii>>q;
	for(register int i=1;i<=tot;i++)
	{
		node[i].dis=0x3f3f3f3f;
	}
	node[1].dis=0;
	q.push({0,1});
	while(q.size())
	{
		pii tmp=q.top();
		q.pop();
		int d=tmp.first,u=tmp.second;
		if(d!=node[u].dis)continue;
		for(int e=node[u].head;e;e=edge[e].next)
		{
			int v=edge[e].to;
			if(node[v].dis>d+edge[e].len)
			{
				node[v].dis=d+edge[e].len;
				q.push({node[v].dis,v});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
	{
		scanf("%s",c[i]+1);
		for(register int j=1;j<=m;j++)
			ord[i][j]=++tot;
		ord[i][m+1]=++tot;
	}
	for(register int i=1;i<=m+1;i++)
	{
		ord[n+1][i]=++tot;
	}
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		{
			if(c[i][j]=='/')
			{
				addEdge(ord[i][j],ord[i+1][j+1],1);
				addEdge(ord[i+1][j+1],ord[i][j],1);
				addEdge(ord[i][j+1],ord[i+1][j],0);
				addEdge(ord[i+1][j],ord[i][j+1],0);			
			}
			if(c[i][j]=='\\')
			{
				addEdge(ord[i][j],ord[i+1][j+1],0);
				addEdge(ord[i][j+1],ord[i+1][j],1);
				addEdge(ord[i+1][j+1],ord[i][j],0);
				addEdge(ord[i+1][j],ord[i][j+1],1);
			}
		}
	}
	Dijkstra();
	if(node[tot].dis!=0x3f3f3f3f)cout<<node[tot].dis<<endl;
	else puts("NO SOLUTION");
	return 0;
}
2021/10/6 18:16
加载中...