看题解学习的Dijkstra求最短路思路但不知道为啥没过
还有只更新次短路要不要入队啊qwq
然而我入不入队都40肯定哪里写挂了但没看出来太蒻了
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=5010,M=1e5+10;
LL n,m;
LL h[N],ne[N],enter[M*2],data[M*2],dis[M*2],dis2[M*2],idx;
bool vis[N];
void add(LL u,LL v,LL w)
{
enter[idx]=v;
ne[idx]=h[u];
data[idx]=w;
h[u]=idx++;
}
void Dijkstra()
{
memset(dis,0x3f,sizeof dis); memset(dis2,0x3f,sizeof dis2); memset(vis,0,sizeof vis);
typedef pair<LL,LL> PLL;
priority_queue< PLL, vector<PLL>, greater<PLL> > q;
q.push({0,1}); dis[1]=0;
while(q.size())
{
PLL New=q.top();q.pop();
LL x=New.second;
if(vis[x]) continue;
vis[x]=true;
for(int i=h[x];i!=-1;i=ne[i])
{
LL v=enter[i],d=data[i];
if(dis[v]>dis[x]+d)
{
dis2[v]=dis[v];
dis[v]=dis[x]+d;
q.push({d,v});
}
else if(dis2[v]>dis[x]+d&&dis[v]<dis[x]+d)
{
dis2[v]=dis[x]+d;
q.push({d,v});
}
else if(dis2[v]>dis2[x]+d)
{
dis2[v]=dis2[x]+d;
q.push({d,v});
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
LL u,v,w;
cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
Dijkstra();
cout<<dis2[n];
}