Subway
> ***|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
题目大意：
给你俩个坐标第一个为家，第二个为学校。
之后每一行给出一条地铁线路，给个线路相邻的俩个站点连通，每一条地铁线以-1 -1 结束。最多200个站点;
步行速度10km/h 地铁40km/h;
难点是建图，用链接矩阵储存，如果是同一条线路且为上一个站点time=d /(40 * 1000 / 60);否则为d /(10 * 1000/60)，在nmap[i][j]比较取小
最后ans四舍五入;
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
const int maxn=505;
using namespace std;
double nmap[maxn][maxn],d[maxn];
struct node{
int x,y;
}e[maxn];
int vis[maxn],m,tot=0;
double len(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void spfa(int st)
{
memset(vis,0,sizeof(vis));
memset(d,125,sizeof(d));
queue<int>q;
q.push(st);
vis[st]=1;
d[st]=0;
while(q.size())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=1;i<=tot;i++)
{
double w=nmap[now][i];
if(d[i]>d[now]+w)
{
d[i]=d[now]+w;
if(vis[i]==0)
{
vis[i]=1;
q.push(i);
}
}
}
}
}
int main(){
int x,y,last=3;
memset(nmap,125,sizeof(nmap));
while(scanf("%d%d",&x,&y)!=EOF)
{
if(x==-1&&y==-1)
{
last=tot+1;
continue;
}
else
{
e[++tot]=(node){x,y};
for(int j=1;j<=tot;j++)
{
double tmp=len(e[tot],e[j]);
if(j==tot-1&&j>=last) tmp/=(40.0*1000/60);
else tmp/=(10.0*1000/60);
nmap[j][tot]=nmap[tot][j]=min(nmap[tot][j],tmp);
}
}
}
spfa(1);
printf("%d
",(int)floor(d[2]+0.5));
return 0;
}