MLE求助优化
查看原帖
MLE求助优化
777848
superkkkeee楼主2023/11/7 17:33

MLE了,62MB够用吗??

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
	int v;
	int w;
};
vector<node> p[100001];
vector<int> lj[100001];
const int inf=0x3f3f3f3f;
void hs(int s)
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	bool vis[100001];
	int dis[100001];
	for(int i=1;i<=n;i++)
	{
		vis[i]=0;
		dis[i]=inf;
	}
	dis[s]=0;
	lj[s].push_back(s);
	q.push({0,s});
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(node xx:p[x])
		{
			int v=xx.v;
			int w=xx.w;
			if(dis[x]+w<dis[v])
			{
				dis[v]=dis[x]+w;
				lj[v]=lj[x];
				lj[v].push_back(v);
				q.push({dis[v],v});
			}
		}
	}
	if(dis[n]==inf) 
	{
		cout<<-1;
		exit(0);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		p[u].push_back({v,w});
		p[v].push_back({u,w});
	}
	hs(1);
	{
		for(int x:lj[n])
		{
			cout<<x<<" ";
		}
	}
	return 0;
}
2023/11/7 17:33
加载中...