题目大意：给你一个二维地图，起点终点，以及多条地铁线路（只有相邻两站才可互通）中的站点坐标。步行以及坐地铁的速度；
思路：难点在于建图，一个多小时磨磨蹭蹭，都是因为思路没捋清楚~~，对于每一条地铁线，在输入站点坐标的过程中我们就可以建立图像了；输入完成后，遍历所有的点再建立，以步行为计量单位的图像。就ok啦，然后裸spfa就好了
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e5 + 2e2;
struct Point
{
double x,y;
Point (double x = 0.0,double y = 0.0):x(x),y(y){}
}ps[maxn];
struct node
{
int to,pre;
double v;
}edge[maxn];
double d[maxn];
int vis[maxn];
int id[maxn];
int cnt;
int nump;
void init()
{
memset(vis,0 ,sizeof(vis));
memset(id,-1,sizeof(id));
cnt = 0;
nump = 2;
}
void add(int from,int to,double v)
{
edge[cnt].to = to;
edge[cnt].v = v;
edge[cnt].pre = id[from];
id[from] = cnt++;
} double disget(int i,int j)
{
return sqrt((ps[i].x - ps[j].x) * (ps[i].x - ps[j].x) +
(ps[i].y - ps[j].y) * (ps[i].y - ps[j].y));
}
queue<int>q;
void spfa(int s)
{
q.push(s);
vis[s] = 1;
d[s] = 0;
while(q.size())
{
int now = q.front();q.pop();
vis[now] = 0;
for(int i = id[now];~i;i = edge[i].pre)
{
if(d[edge[i].to] > d[now] + edge[i].v)
{
d[edge[i].to] = d[now] + edge[i].v;
if(!vis[edge[i].to])
{
vis[edge[i].to] = 1;
q.push(edge[i].to);
}
}
}
}
}
int main()
{
init();
double x,y;
scanf("%lf%lf",&x,&y);
ps[0]=Point(x,y);
scanf("%lf%lf",&x,&y);
ps[1] = Point(x,y);
d[1] = inf;
while(~scanf("%lf%lf",&x,&y))
{
ps[nump] = Point(x,y);
d[nump++] = inf;
while(~scanf("%lf%lf",&x,&y) && x != -1 && y != -1)
{
ps[nump] = Point(x,y);
double v = disget(nump,nump-1) / (1000.0 * 40.0) * 60.0;
//cout<<v<<endl;
add(nump - 1,nump,v);
add(nump,nump - 1,v);
d[nump++] = inf;
}
}
for(int i = 0;i < nump;i++)
{
for(int j = 0;j < nump;j++)
{
double v = disget(i,j) / (1000 * 10) * 60;
//cout<<v<<endl;
add(i,j,v);
}
}
spfa(0);
printf("%d\n",int(d[1] + 0.5));
return 0;
}