你可想象，当你在一个大城市中，你想从 A 点到 B点，因此你必须步行或乘地铁。乘地铁肯定比步行快，但你必须从地铁站进出。为了节省时间，你决定写一程序，找一条最快的路线。
input：
输入文件的第一行有两个浮点数。第一行为步行速度，第二个为乘地铁的速度，第二个总比第一个大。
接下来的就是地铁的描述。第一行为一整数 N ，它是地铁站的数量。假设N不超过 200。接下来的N行，每行包含两个浮点数 (第i-行为第 i-个地铁站的坐标)。接下来的描述表示哪两个站相连，每一连接用一对整数描述，也一就是说，连接的两个站的编号。用一对数0，0表示连接的终止。假设所有的连接都是直线。
注意，转换交通工具只能在地铁的出入站口，并且不花时间。
最后为点 A 和 B 的坐标，一行一个。
output：
第一行为从点A到点B所需的最少时间，精确至小数点后 10-6位。第二行为旅行时利用的地铁站的描述。第一个为访问的地铁站的数量，后跟着一系列地铁站的编号。
input：
1 100
4
0 0
1 0
9 0
9 9
1 2
1 3
2 4
0 0
10 10
10 0
output：
2.6346295
4 4 2 1 3
【参考程序】：
#include<iostream>//以点与点间的距离为边，能走地铁的尽量走，其他的就foot
#include<cmath>
using namespace std;
struct node
{
double x,y;
} p[210];
double dis[210][210];
int ans[210],pre[210][210];
double vf,vt;
int n,len;
void find_path(int p)
{
if (pre[p][n+1]==n+1) return ;
len++;ans[len]=pre[p][n+1];
find_path(pre[p][n+1]);
}
int main()
{
scanf("%lf%lf",&vf,&vt);
scanf("%d",&n);
for (int i=0;i<=n+1;i++)
for (int j=0;j<=n+1;j++)
if (i==j) dis[i][j]=0;
else dis[i][j]=0xFFFFFFF;
for (int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int a,b;double s1,s2;
while (scanf("%d%d",&a,&b),a+b!=0)
{
s1=p[a].x-p[b].x;s2=p[a].y-p[b].y;
dis[a][b]=(sqrt(s1*s1+s2*s2))/vt;
pre[a][b]=b;
dis[b][a]=dis[a][b];pre[b][a]=a;
}
scanf("%lf%lf",&p[0].x,&p[0].y);
scanf("%lf%lf",&p[n+1].x,&p[n+1].y);
for (int i=0;i<=n+1;i++)
for (int j=0;j<=n+1;j++)
if (dis[i][j]==0xFFFFFFF)
{
s1=p[i].x-p[j].x;s2=p[i].y-p[j].y;
dis[i][j]=(sqrt(s1*s1+s2*s2))/vf;
pre[i][j]=j;
}
for (int k=0;k<=n+1;k++)
for (int i=0;i<=n+1;i++)
if (i!=k)
for (int j=0;j<=n+1;j++)
if (i!=j && k!=j)
if (dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
pre[i][j]=pre[i][k];
}
printf("%0.7lf\n",dis[0][n+1]);
len=0;
find_path(0);
printf("%d",len);
for (int i=1;i<=len;i++) printf(" %d",ans[i]);
printf("\n");
return 0;
}