HELP!pts40
查看原帖
HELP!pts40
540177
wyf_sinon楼主2023/6/10 15:19

看题解学习的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];
}
2023/6/10 15:19
加载中...