POJ 2502 【思维是朴素的最短路 卡输入和建图】

题意：

给出两个坐标，分别是小明家和小明学校的坐标。

给出多条地铁线，给出每站的坐标，已知地铁是双向的，每条线以-1 -1结尾。

给出地铁速度，步行速度。

地铁线可看成是顺次连接的线段。

求小明从家到学校用到的时间。

思路：

任何两点之间都可以连速度为步行的无向边，地铁相邻两站可以连速度为地铁速度的无向边。

之后进行SPFA；

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<queue>

using namespace std;

const int inf=;

double dis[];

bool vis[];

double numa=500.0/;

double numb=2000.0/;

struct node

{

    double x,y;

};

node nodes[];

struct edge

{

    int id;

    double mint;

    edge *next;

};

edge edges[];

edge *adj[];

int ednum;

int num;

double cal(int a,int b,double c)

{

    return sqrt((nodes[a].x-nodes[b].x)*(nodes[a].x-nodes[b].x)+(nodes[a].y-nodes[b].y)*(nodes[a].y-nodes[b].y))/c;

}

inline void addEdge(int a,int b,double c)

{

    edge *tmp;

    tmp=&edges[ednum];

    ednum++;

    tmp->id=b;

    tmp->mint=c;

    tmp->next=adj[a];

    adj[a]=tmp;

}

void SPFA()

{

    memset(vis,,sizeof(vis));

    for(int i=;i<num;i++)

    {

        dis[i]=inf;

    }

    queue<int>q;

    q.push();

    vis[]=;

    dis[]=;

    while(!q.empty())

    {

        int tmp=q.front();

        q.pop();

        vis[tmp]=;

        for(edge *p=adj[tmp];p;p=p->next)

        {

            if(p->mint+dis[tmp]<dis[p->id])

            {

                dis[p->id]=p->mint+dis[tmp];

                if(!vis[p->id])

                {

                    q.push(p->id);

                    vis[p->id]=;

                }

            }

        }

    }

}

int main()

{

    for(int i=;i<=;i++)

    {

        adj[i]=NULL;

    }

    ednum=;

    num++;

    scanf("%lf%lf",&nodes[num].x,&nodes[num].y);

    num++;

    scanf("%lf%lf",&nodes[num].x,&nodes[num].y);

    num++;

    while(scanf("%lf%lf",&nodes[num].x,&nodes[num].y)!=EOF)

    {

        num++;

        while(scanf("%lf%lf",&nodes[num].x,&nodes[num].y))

        {

            if(nodes[num].x<&&nodes[num].y<)

                break;

            num++;

            addEdge(num-,num-,cal(num-,num-,numb));

            addEdge(num-,num-,cal(num-,num-,numb));

        }

    }

    for(int i=;i<num;i++)

    {

        for(int j=;j<i;j++)

        {

            addEdge(i,j,cal(i,j,numa));

            addEdge(j,i,cal(i,j,numa));

        }

    }

    SPFA();

    printf("%.0lf\n",dis[]);

}