# 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

```#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
{
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];
double dist[345];
bool vis[345];
{
e[++cnt].lon=lon;
e[cnt].to=to;
}
int main()
{
node[++num][0]=x1;
node[num][1]=y1;
node[++num][0]=x2;
node[num][1]=y2;
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);
}
}
for(int i=2; i<=num; i++)
dist[i]=2e8;
t[0]=1;
{
while(r!=-1)
{
{
if(!vis[e[r].to])
{
vis[e[r].to]=1;
t[tail++]=e[r].to;
}
}
r=e[r].next;
}
}
printf("%f",dist[2]);
return 0;
}

//    FOR C.H```

```#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct edge
{
int next,to;
double lon;
} e[4045];
{
e[++cnt].lon=lon;
e[cnt].to=to;
}
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;
}
s=0;
continue;
}
map[++num][0]=x;
map[num][1]=y;
s++;
}
}
double dist[345];
bool vis[345];
int main()
{
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;
}
num++;
for(int i=1; i<num; i++)
{
double f=far(map[i][0],map[i][1],x1,y1)/1000*6;
}
num++;
for(int i=1; i<num-1; i++)
{
double f=far(map[i][0],map[i][1],x2,y2)/1000*6;
}
t[0]=num-1;
vis[num-1]=1;
for(int i=1; i<=num; i++)
dist[i]=2e8;
dist[num-1]=0;
{
printf("r=%d\n",r);
while(r!=-1)
{
{
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;
}
}
printf("%d",change(dist[num]));
return 0;
}

//    FOR C.H```

## 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 (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，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

## 【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