POJ-2502 Subway( 最短路建图 )

本文主要是介绍POJ-2502 Subway( 最短路建图 )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

人走路的速度是10km/h，地铁的速度是40km/h题目给出一个起点，一个终点，以及几条地铁线路运行的站点。

题目给的点的做坐标单位是m把速度统一为m/min，答案输出从起点到终点的时间，到最近的分钟数。10km/h= 10000/60 m/min，40km/h= 40000/60 m/min

所有的点直接以步行的速度建边。地铁线路两站相邻的以地铁速度建边

总结：这题主要在于建图与输入

#include<cstdio>
#include<algorithm>
#include<string.h>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<map>
#include<vector>
#include<ctype.h>
#include<set>
#include<queue>
using namespace std;

const int maxn=1006;
const double inf=1e30;
struct node{double x,y;}k[maxn];
double a[maxn][maxn];
double dist[maxn];
int vis[maxn];
int n;

double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void Dijkstra(int n)
{
//memset(dist,inf,sizeof(dist));
memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
   {
        dist[i]=inf;
    }
    dist[1]=0;
    for(int i=1;i<=n;i++)
    {
        int k=-1;
        double Min=inf;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<Min)
            {
                Min=dist[j];
                k=j;
            }
        if(k==-1)break;
        vis[k]=true;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[k]+a[k][j]<dist[j])
                dist[j]=dist[k]+a[k][j];
    }
}

void init(void){
        for(int i=1;i<300;i++)
            for(int j=1;j<300;j++)
            {
                if(i==j)a[i][j]=0;
                else a[i][j]=inf;
            }
}
int main(){
double v1=10000.0/60;
double v2=40000.0/60;
while(scanf("%lf%lf%lf%lf",&k[1].x,&k[1].y,&k[2].x,&k[2].y )==4){
  n=2;
  int cnt=3;
  init();
  int x,y;
        while(scanf("%d%d",&x,&y)==2)
        {
            if(x==-1&&y==-1)
            {
                cnt=n+1;
                continue;
            }
            n++;
            k[n].x=x;
            k[n].y=y;
            if(n!=cnt)a[n][n-1]=a[n-1][n]=min(a[n][n-1],dis(k[n],k[n-1])/v2);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],dis(k[i],k[j])/v1);
  Dijkstra(n);
  printf("%.0f\n",dist[2]);
}
}

这篇关于POJ-2502 Subway( 最短路建图 )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！