Dijkstra【p3003(bzoj2100)】[USACO10DEC]苹果交货Apple Delivery

Description

贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的C（1<=C<=200000）条“牛路”都被包含在一种常用的图中，包含了P（1<=P<=100000）个牧场，分别被标为1..P。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场P1_i和P2_i（1<=P1_i,p2_i<=P)，距离为D_i。所有“牛路”的距离之和不大于2000000000。

现在，贝西要从牧场PB开始给PA_1和PA_2牧场各送一个苹果（PA_1和PA_2顺序可以调换），那么最短的距离是多少呢？当然，PB、PA_1和PA_2各不相同。

Input

第一行,5个整数,\(C,P,PB,PA1,PA2\)(含义如题所述)

接下来\(C\)行,每行三个整数\(x,y,z\)描述一条无向边。

Output

一个整数，代表最小距离.

难得遇到一个这么裸的最短路题。

貌似\(Spfa\)会被\(Hack\)？

直接写\(Dijkstra\)。

分别以\(PA1\)，\(PA2\)为起点跑\(Dijkstra\)。

每次对于到达其他两个点的距离取\(min\)即可。

代码

#include<cstdio>

#include<algorithm>

#include<queue>

#include<iostream>

#define R register

using namespace std;

const int gz=200008;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int m,n,s,a,b,ans=214748364;

int head[gz],tot,dis[gz];

bool vis[gz];

struct hop

{

	int u,d;

	bool operator <(const hop&a)const

	{

		return d>a.d;

	}

};

struct cod{int u,v,w;}edge[gz<<2];

inline void add(R int x,R int y,R int z)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	edge[tot].w=z;

	head[x]=tot;

}

inline void dijkstra(R int s)

{

	for(R int i=1;i<=n;i++)dis[i]=214748364,vis[i]=false;

	priority_queue<hop>q;

	q.push((hop){s,dis[s]=0});

	while(!q.empty())

	{

		R int u=q.top().u;q.pop();

		if(vis[u])continue;

		vis[u]=true;

		for(R int i=head[u];i;i=edge[i].u)

		{

			if(dis[edge[i].v]>dis[u]+edge[i].w)

			{

				dis[edge[i].v]=dis[u]+edge[i].w;

				q.push((hop){edge[i].v,dis[edge[i].v]});

			}

		}

	}

}

int main()

{

	in(m),in(n),in(s),in(a),in(b);

	for(R int i=1,x,y,z;i<=m;i++)

	{

		in(x),in(y),in(z);

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

	}

	dijkstra(a);

	ans=min(ans,dis[b]+dis[s]);

	dijkstra(b);

	ans=min(ans,dis[a]+dis[s]);

	printf("%d",ans);

}

巴特西

Dijkstra【p3003(bzoj2100)】[USACO10DEC]苹果交货Apple Delivery

Description

Input

Output

最新文章

热门文章