path

5 1 31 33 44 17 58 3

18.18【样例解释】    最短路径：0->1->4->3->2->0

对于所有数据x,y,b1,b2如题目描述.

#include<iostream>#include<cstdio>#include<cmath>using namespace std;int a,b,c,d,e,v[2001][2];double r[2001][2001],f[2001][2001],ans;double dp(int,int);int main(){	freopen("path.in","r",stdin);	freopen("path.out","w",stdout);	scanf("%d%d%d",&a,&b,&c);	b++;	c++;	for (d=1;d<=a;d++)		scanf("%d%d",&v[d][1],&v[d][2]);	for (d=1;d<=a-1;d++)		for (e=d+1;e<=a;e++)			r[d][e]=sqrt((v[d][1]-v[e][1])*(v[d][1]-v[e][1])+(v[d][2]-v[e][2])*(v[d][2]-v[e][2]));	for (d=1;d<=a;d++)		for (e=1;e<=a;e++)			f[d][e]=-1;	ans=dp(1,1);	printf("%.2lf",ans);}double dp(int i,int j){	int k;	if (f[i][j]==-1)	{		if (i>j)			k=i;		else			k=j;		if (k==a)			f[i][j]=0;		else		{			if (k+1==b)			f[i][j]=r[i][b]+dp(b,j);            	else            if (k+1==c)             f[i][j]=r[j][c]+dp(i,c);            	else            if (k+1==a)             f[i][j]=r[i][a]+r[j][a]+dp(a,a);        		else            f[i][j]=min(r[i][k+1]+dp(k+1,j),r[j][k+1]+dp(i,k+1));		}	}	return f[i][j];}