bzoj 2100: [Usaco2010 Dec]Apple Delivery【spfa】

洛谷数据好强啊，普通spfa开o2都过不了，要加双端队列优化

因为是双向边，所以dis(u,v)=dis(v,u)，所以分别以pa1和pa2为起点spfa一遍，表示pb-->pa1-->pa2和pb-->pa2-->pa1，取个min即可

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=200005,inf=2e9+7;

int m,n,a,b1,b2,h[N],cnt,dis[N];

bool v[N];

struct qwe

{

	int ne,to,va;

}e[N<<2];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void spfa(int s)

{

	deque<int>q;

	for(int i=1;i<=n;i++)

		dis[i]=inf;

	dis[s]=0,v[s]=1,q.push_back(s);

	while(!q.empty())

	{

		int u=q.front();

		q.pop_front();

		v[u]=0;

		for(int i=h[u];i;i=e[i].ne)

			if(dis[e[i].to]>dis[u]+e[i].va)

			{

				dis[e[i].to]=dis[u]+e[i].va;

				if(!v[e[i].to])

				{

					v[e[i].to]=1;

					if(!q.empty()&&dis[q.front()]>dis[e[i].to])

						q.push_front(e[i].to);

					else

						q.push_back(e[i].to);

				}

			}

	}

}

int main()

{

	m=read(),n=read(),a=read(),b1=read(),b2=read();

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read(),z=read();

		add(x,y,z),add(y,x,z);

	}

	spfa(b1);

	int ans=dis[a]+dis[b2];

	spfa(b2);

	printf("%d\n",min(ans,dis[a]+dis[b1]));

	return 0;

}