POJ 2502 Subway-经过预处理的最短路

Description

You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don‘t want to be late for class, you want to know how long it will take you to get to school. 
You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.

Input

Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.

Output

Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.

Sample Input

0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1

Sample Output

21

Source

Waterloo local 2001.09.22


这道题的思路简单来说就是将所有地铁站转换成点,然后预处理所有点间的边权(即将距离转换成时间),然后用最短路算法(例如SPFA)求出起点和目标点的距离。

但是!!!

说的简单,实现起来真TM麻烦。

第一:

需要四舍五入得到答案。

四舍五入的函数不难写,但是在哪里四舍五入是个问题。

回忆了一下做数学题的教训,前面一直用double保存边权,到最后再四舍五入误差最小。

第二:

每点间的距离处理。

你需要判断他们间的路是在地铁里还是人行道,所以我加了一个初始为1的变量p,每次输入-1,-1是就p++。

然后每次在两点间赋权的时候判断是不是在同一条地铁线上。

第三:
现在还没解决的问题,如果两条地铁线交叉,那么赋权就又有问题了,所以我希望可以用坐标来表示点,但是由于坐标可能给的很大,所以一直不知道怎么处理。

附上还没完成的代码(甚至样例都是错的),希望可以有所启发(还会不断更新,知道附上AC代码):

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
int read()
{
    int x=0,y=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)
    {
        if(ch==‘-‘)
            y=-1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘)
    {
        x=x*10+ch-‘0‘;
        ch=getchar();
    }
    return x*y;
}
int abs(int x)
{
    if(x<0)
        return -x;
    else
        return x;
}
int change(double x)
{
    int r=(int)x;
    if(x-r<0.5)
        return r;
    else
        return r+1;
}
double way(int x1,int y1,int x2,int y2)
{
    int r1=abs(x1-x2),r2=abs(y1-y2);
    return sqrt(r1*r1+r2*r2);
}
struct edge
{
    int next,to;
    double lon;
} e[4045];
int map[305][305],num,node[305][3],head[6045],cnt,t[345],headd,tail=1;
double dist[345];
bool vis[345];
void add(int from,int to,double lon)
{
    e[++cnt].lon=lon;
    e[cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
int main()
{
    memset(head,-1,sizeof(head));
    int x1=read(),y1=read(),x2=read(),y2=read(),x,y,p=1,l=change(way(x1,y1,x2,y2)/1000*6);
    node[++num][0]=x1;
    node[num][1]=y1;
    node[++num][0]=x2;
    node[num][1]=y2;
    add(1,2,l);
    add(2,1,l);
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        if(x==-1&&y==-1)
        {
            p++;
            continue;
        }
        node[++num][0]=x;
        node[num][1]=y;
        node[num][2]=p;
        for(int i=1; i<num; i++)
        {
            double dis;
            if(node[i][2]==p)
                dis=way(x,node[i][0],y,node[i][1])/4000*6;
            else
                dis=way(x,node[i][0],y,node[i][1])/1000*6;
//            printf("x=%d y=%d node[i][0]=%d node[i][1]=%d dis=%f\n",x,y,node[i][0],node[i][1],dis);
            add(num,i,dis),add(i,num,dis);
        }
    }
    for(int i=2; i<=num; i++)
        dist[i]=2e8;
    t[0]=1;
    while(headd!=tail)
    {
        int r=head[t[headd]];
        vis[t[headd]]=0;
        while(r!=-1)
        {
            if(dist[e[r].to]>dist[t[headd]]+e[r].lon)
            {
                dist[e[r].to]=dist[t[headd]]+e[r].lon;
                printf("e[r].lon=%f e[r].to=%d dist=%f %f\n",e[r].lon,e[r].to,dist[t[headd]],dist[e[r].to]);
                if(!vis[e[r].to])
                {
                    vis[e[r].to]=1;
                    t[tail++]=e[r].to;
                }
            }
            r=e[r].next;
        }
        headd++;
    }
    printf("%f",dist[2]);
    return 0;
}

//    FOR C.H

附上最新经谭姐启发写的正解方法代码(思路稍后,仍有问题在调试):

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int head[4045],cnt,num;
struct edge
{
    int next,to;
    double lon;
} e[4045];
void add(int from,int to,double lon)
{
    e[++cnt].lon=lon;
    e[cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
int abs(int x)
{
    if(x<0)
        return -x;
    else
        return x;
}
double far(int x1,int y1,int x2,int y2)
{
    int r1=abs(x1-x2),r2=abs(y1-y2);
    return sqrt(r1*r1+r2*r2);
}
int change(double x)
{
    int r=(int)x;
    if(x-r<0.5)
        return r;
    else
        return r+1;
}
int sub[345][2],map[345][2];
void scan()
{
    int x,y,p=0,s=0;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        if(x==-1&&y==-1)
        {
            for(int i=2; i<=s; i++)
            {
                double f=far(map[num-s+i-1][0],map[num-s+i-1][1],map[num-s+i][0],map[num-s+i][1])/4000*6;
                add(num-s+i-1,num-s+i,f);
                add(num-s+i,num-s+i-1,f);
            }
            s=0;
            continue;
        }
        map[++num][0]=x;
        map[num][1]=y;
        s++;
    }
}
double dist[345];
int t[345],headd,tail=1;
bool vis[345];
int main()
{
    memset(head,-1,sizeof(head));
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    scan();
    for(int i=1; i<=num; i++)
        for(int j=1; j<=num; j++)
        {
            double f=far(map[i][0],map[i][1],map[j][0],map[j][1])/1000*6;
            add(i,j,f);
        }
    num++;
    for(int i=1; i<num; i++)
    {
        double f=far(map[i][0],map[i][1],x1,y1)/1000*6;
        add(i,num,f);
        add(num,i,f);
    }
    num++;
    for(int i=1; i<num-1; i++)
    {
        double f=far(map[i][0],map[i][1],x2,y2)/1000*6;
        add(i,num,f);
        add(num,i,f);
    }
    t[0]=num-1;
    vis[num-1]=1;
    for(int i=1; i<=num; i++)
        dist[i]=2e8;
    dist[num-1]=0;
    while(headd!=tail)
    {
        int r=head[t[headd]];
        printf("r=%d\n",r);
        while(r!=-1)
        {
            if(dist[e[r].to]>dist[t[headd]]+e[r].lon)
            {
                dist[e[r].to]=dist[t[headd]]+e[r].lon;
                printf("dist[e[r].to]=%f\n",dist[e[r].to]);
                if(!vis[e[r].to])
                {
                    vis[e[r].to]=1;
                    t[tail++]=e[r].to;
                }
            }
            r=e[r].next;
        }
        headd++;
    }
    printf("%d",change(dist[num]));
    return 0;
}

//    FOR C.H
时间: 07-10

POJ 2502 Subway-经过预处理的最短路的相关文章

POJ 2502 SUBWAY(最短路)

POJ 2502 SUBWAY 题目链接:http://poj.org/problem?id=2502 题目大意:求从a点到b点所需要的最短时间. 题目思路:用最短路来求,把各个点之间的时间看作所需要的路程.然后用 dij求最短路就可以了,感觉输入有点坑,还有在每条地铁线上,只有相同地铁线上的 点可以互相到达. #include<stdio.h> #include<algorithm> #include<math.h> using namespace std; cons

POJ 2502 Subway(最短路径)

原题地址:http://poj.org/problem?id=2502 Subway Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7347   Accepted: 2387 Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bi

POJ 2502 Subway (Dijkstra 最短路+建图)

Subway Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6689   Accepted: 2176 Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get

POJ 2502 Subway(迪杰斯特拉)

Subway Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6692   Accepted: 2177 Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get

poj 2502 Subway

题目链接: http://poj.org/problem?id=2502 题目大意: 一个学生去上学,从家到学校,可以有若干个地铁路线,每个地铁路线有若干站,给出步行和地铁的速度,问:最短用多长时间从家到达学校? 解题思路: 有地铁的两点建立地铁路线,没有的步行,求最短路,但是有一点坑的是地铁线有可能是曲线,也就是说从a站到b站再到c站的距离和大于a站直接到c站的距离 1 #include <cstdio> 2 #include <cstring> 3 #include <c

(简单) POJ 2502 Subway,Dijkstra。

Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know

Dijkstra+计算几何 POJ 2502 Subway

题目传送门 题意:列车上行驶40, 其余走路速度10.问从家到学校的最短时间 分析:关键是建图:相邻站点的速度是40,否则都可以走路10的速度.读入数据也很变态. #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 2e2 + 5; const i

【POJ】2449 Remmarguts&#39; Date(k短路)

http://poj.org/problem?id=2449 不会.. 百度学习.. 恩. k短路不难理解的. 结合了a_star的思想.每动一次进行一次估价,然后找最小的(此时的最短路)然后累计到k 首先我们建反向边,跑一次从汇到源的最短路,将跑出来的最短路作为估价函数h 根据f=g+h 我们将源s先走,此时实际价值g为0,估价为最短路(他们的和就是s-t的最短路) 将所有s所连的边都做相同的处理,加入到堆中(假设此时到达的点为x,那么x的g等于s到这个点的边权,因为根据最优,g+h此时是从x

POJ 3114 Countries in War 强连通+最短路

用floyd超时了...注定的事情...题意:看案例就跑出来了..不需要看题了把.. #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #include<vector> const int INF =1999299; int minn(int a,int b) { return a>b?b:a; } #define N 510 #define M