问一个问题
查看原帖
问一个问题
643735
RNTBW楼主2023/2/12 18:44

为啥这代码会TLE捏?

我知道做法可能是假的,我也懂题解的做法,但是我就是不懂为啥TLE/yiw

#include<bits/stdc++.h>
using namespace std;
#define mxn 10001
#define int long long
int head[mxn];
int n,m,cnt,ans=1e18,accept=1e18;
bool arr[mxn];
struct eve
{
	int u,v,t,nxt;
} es[mxn<<5];
struct bfsr
{
	int bf;int di;
	bfsr(int bf_,int di_){ bf=bf_;di=di_; }
};
bool operator<(bfsr a,bfsr b){return a.di>b.di;}
void add(int x,int y,int z)
{
	es[++cnt].u=x;
	es[cnt].v=y;
	es[cnt].t=z;
	es[cnt].nxt=head[x];
	head[x]=cnt;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	priority_queue<bfsr> pq;
	pq.push(bfsr(1,0));
	while(pq.size())
	{
		int las=pq.top().bf,len=pq.top().di;
		pq.pop();
		if(las==n)
		{
			if(ans==1e18)ans=len;
			else if(ans<len&&ans<1e18)
			{accept=len;break;
			}
		}
		for(int j=head[las];j!=0;j=es[j].nxt)
		{
			int to=es[j].v;
			pq.push(bfsr(to,len+es[j].t));
		}
	}
	printf("%lld",accept);
	return 0;
}
2023/2/12 18:44
加载中...