题意：
你从家往学校赶，可以用步行和乘坐地铁这两种方式，步行速度为10km/h，乘坐地铁的速度为40KM/h。输入数据的第一行数据会给你起点和终点的x和y的坐标。然后会给你数目不超过200的双向地铁线路的站点，你可以从一个站点乘坐地铁到下一个站点，你可以在同一线路上乘坐地铁经过不同的站点，在不同线路的站点之间，你只能用步行的方式。让你求利用你可以利用的方式，求解到校花费的最短时间。
思路：
基础最短路径问题，Dijkstra算法可以解决。需要特别注意以下输入数据的方式，这道题目没有很明显的输入结束标志，要用scanf()！= EOF来进行判断。然后把图的信息存入 map数组里面，当i到j在一条铁路线路上的时候，用它的距离除以40000来求解时间并存入map[i][j]中，map其他的位置存储不行的时间，然后套用模板直接求解最短路径就可以了。
#include<iostream>
#include<cmath>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std; const double INF=100000000.0; struct Point
{
double x;
double y;
}p[205]; bool visited[205];
int n;
double d[205];
double map[205][205];
double getLen(Point p1,Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void Dijkstra(){
int i,j,u;
double temp;
visited[0]=true;
for(i=0;i<n;i++)
d[i]=map[0][i];
for(i=1;i<n;i++)
{
temp=INF;
for(j=0;j<n;j++)
if(!visited[j]&&d[j]<temp)
{
temp=d[j];
u=j;
}
visited[u]=true;
for(j=0;j<n;j++)
if(!visited[j])
{
temp=d[u]+map[u][j];
if(temp<d[j])
d[j]=temp;
}
}
}
int main()
{
int i,j;
double temp;
bool flag=false;
scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y); //起始位置和目的地坐标
n=2;
memset(map,0,sizeof(map));
while(~scanf("%lf%lf",&p[n].x,&p[n].y))
{
if(p[n].x==-1&&p[n].y==-1)
{
flag=false;
continue;
}
if(flag) //有效的处理了只输入第一个点时不产生线段
{
temp=getLen(p[n],p[n-1])/40000.0; //存储的是时间（小时）,地铁的速度是40km/h
map[n][n-1]=map[n-1][n]=temp;
}
n++;
flag=true;
}
//得到所有步行段的距离 一共n（2+(n-2)）个点
for(i=0;i<n;i++) //计算需要步行的所用的时间
for(j=0;j<n;j++)
if(i!=j&&map[i][j]==0.0)//初始是0.0(步行段)
map[i][j]=map[j][i]=getLen(p[i],p[j])/10000.0; //步行的速度是10km/h memset(visited,0,sizeof(visited));
//Dijkstra算法求解最短路
Dijkstra(); //题目所要求的单位是分钟
printf("%0.0lf\n",60.0*d[1]);
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。