1938: 蓝桥杯算法提高VIP-道路和航路

解题思路:有负权的单源最短路径,使用spfa算法即可

注意事项:不进行SLF优化会超时两个点

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int w;
	int to;
	int next;
}mp[500005];
int head[500005];
int cnt=0;
void add(int a,int b,int c)
{
	mp[++cnt].next=head[a];
	mp[cnt].to=b;
	mp[cnt].w=c;
	head[a]=cnt;
}
int t,r,p,s;
int dis[500005];
int vis[500005];
deque<int>q;
void spfa()
{
	while(!q.empty())
	{
		int x=q.front();
		q.pop_front();
		vis[x]=0;
		for(int i=head[x];i;i=mp[i].next)
		{
			int y=mp[i].to;
			if(dis[x]+mp[i].w<dis[y])
			{
				dis[y]=dis[x]+mp[i].w;
				if(!vis[y])
				{
					vis[y]=1;
					if(!q.empty()&&dis[y]>=dis[q.front()])//SLF优化
					{
						q.push_back(y);
					}
					else
					{
						q.push_front(y);
					}
				}
			}
		}
	}
}
int main()
{
	//cin>>t>>r>>p>>s;
	scanf("%d%d%d%d",&t,&r,&p,&s);
	for(int i=1;i<=r;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=1;i<=p;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	for(int i=1;i<=t;i++)
	{
		dis[i]=0x3f3f3f3f;
	}
	dis[s]=0;
	q.push_back(s);
	vis[s]=1;
	spfa();
	for(int i=1;i<=t;i++)
	{
		if(dis[i]==0x3f3f3f3f)
		{
			//cout<<"NO PATH"<<endl;
			printf("NO PATH\n");
		}
		else
		{
			//cout<<dis[i]<<endl;
			printf("%d\n",dis[i]);
		}
	}
	return 0;
}