Dijkstra--POJ 2502 Subway（求出所有路径再求最短路径）

题意：

你从家往学校赶，可以用步行和乘坐地铁这两种方式，步行速度为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;

}