POJ 2502

题意： 走路10km/h 地铁40km/h 给了家 学校 和每个地铁站的坐标（都是正整数） 问从家到学校的最小时间

思路： 恶心就恶心在建图上 事实上 把所有坐标都编号 家是1 学校是2 然后每个地铁站依次遍为3 4 5 .... 对所有点都有 如果是同一条地铁线上的点 那每两个相邻点的时间花费就是
time = d / (40.0 * 1000.0 / 60.0） 否则 time=d / (10.0 * 1000.0 / 60.0) 用cnt去记录每一条线路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<queue>
using namespace std;

typedef long long ll;
const int maxn=505;
double mp[maxn][maxn],dis[maxn];
int vis[maxn];
int k=0;

struct node{
	int x,y;
}e[maxn];
double far(node a,node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void spfa()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x42,sizeof(dis));
	queue<int> q;
	q.push(1);
	vis[1]=1;
	dis[1]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=1;i<=k;i++)
		{
			double w=mp[u][i];
			if(dis[i]>dis[u]+w)
			{
				dis[i]=dis[u]+w;
				if(!vis[i])
				{
					q.push(i);
					vis[i]=1;
				}
			}
		}
	}
}

int main()
{
	int cnt=3,x,y;	
	memset(mp,0x42,sizeof(mp));
	while(scanf("%d%d",&x,&y)!=EOF)
	{
		if(x==-1 && y==-1)
		{
			cnt=k+1;
			continue;
		}
		else
		{
			e[++k]=(node){x,y};
			for(int i=1;i<=k;i++)
			{
				double sum=far(e[k],e[i]);
				if(i==k-1 && i>=cnt) sum/=(40.0*1000.0/60.0);
				else sum/=(10.0*1000.0/60.0); 
				mp[i][k]=mp[k][i]=min(sum,mp[k][i]);
			}
		}
		
	}
	spfa();
	printf("%d
",(int)floor(dis[2]+0.5));
	return 0;
 }