subway dijkstra

这个题实际上并不难 适合练习dijkstra

#include "stdio.h"
#include "stdlib.h"
#include <cmath>
#define  maxn 1000
#define inf 2000000
double map[maxn][maxn];
double pos[maxn][2];
double d[maxn];
int vis[maxn];
double dist(int x,int y)
{
    return sqrt((pos[x][0]-pos[y][0])*(pos[x][0]-pos[y][0])+(pos[x][1]-pos[y][1])*(pos[x][1]-pos[y][1]));
}
void dijkstra(int n)
{
    for(int i=0;i<=n;i++)
    {
        int x=inf;
        int m = 0;
        for(int j=0;j<=n;j++)
        {
            if(!vis[j]&&d[j]<x) x=d[m=j];
        }
        vis[m]=1;
        for(int j=0;j<=n;j++)
        {
            if(d[m]+map[m][j]<d[j]) d[j]=d[m]+map[m][j];
        }
    }
    return ;
}
int main()
{
    double x,y;
    int cnt=2;
    bool flag=false;
    for(int i=1;i<maxn;i++) d[i]=inf;
    scanf("%lf %lf %lf %lf ",&pos[0][0],&pos[0][1],&pos[1][0],&pos[1][1]);
    map[0][1]=map[1][0]=dist(0,1);
    while(scanf("%lf %lf",&x,&y)!=EOF)
          {
              if(x==-1 &&y==-1)
              {
                  flag=false;
                  continue;
              }
              pos[cnt][0]=x;
              pos[cnt][1]=y;
              if(flag)
              {
                  double d=dist(cnt,cnt-1)*6/4000;
                  map[cnt-1][cnt]=map[cnt][cnt-1]=d;
              }
              flag=true;
              cnt++;
          }
    for(int i=0;i<cnt;i++)
        for(int j=0;j<cnt;j++)
            if(i!=j&&map[i][j]==0) map[i][j]=map[j][i]=dist(i,j)*6/1000;
    dijkstra(cnt-1);
    printf("%.0lf\n",d[1]);
    return 0;
}

只是注意好输入和输出就可以了 注意两点

1.地铁的其中一个站只与前边的站点有距离；

2 其他的站点就是用距离除以10km／h的速度；

下面写代码