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;
}