POJ-2502-Subway

这个题是说给你2个坐标分别是起点和终点，然后给出你一些航线，要求你起点到终点的最短时间。

注意：步行和坐车的速度是不一样的，单位也需要进行一个转换，建图的时候转换为对应的时间作为权值

然后求出起点到终点的最短路径即可

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=501;
const int inf=1<<29;
struct node
{
    int x;
    int y;
}p[maxn];
double map[maxn][maxn],dist[maxn];
bool vis[maxn];
void Init()
{
    for(int i=1;i<maxn;i++)
	for(int j=1;j<maxn;j++)
	    if(i==j)map[i][j]=0;
	    else map[i][j]=inf;
}
double Dis(int i,int j)
{
    return sqrt(1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
}
double Distra(int st,int n)
{
    for(int i=1;i<=n;i++)
	dist[i]=map[st][i];
    memset(vis,0,sizeof(vis));
    for(int i=1;i<n;i++)
    {
	double mini=inf;
	int pos=-1;
	for(int j=1;j<=n;j++)
	    if(!vis[j]&&dist[j]<mini)
	    {
		mini=dist[j];
		pos=j;
	    }
	if(pos==-1)
	    break;
	vis[pos]=1;
	for(int j=1;j<=n;j++)
	    if(!vis[j]&&dist[j]>dist[pos]+map[pos][j])
		dist[j]=dist[pos]+map[pos][j];
    }
    return dist[2];
}
int main()
{
    double v1=40000.0/60.0;
    double v2=10000.0/60.0;
    Init();
    scanf("%d%d%d%d",&p[1].x,&p[1].y,&p[2].x,&p[2].y);
    int n=3,last=3;
    while(scanf("%d%d",&p[n].x,&p[n].y)!=EOF)
    {
	if(p[n].x==-1&&p[n].y==-1)
	{
	    last=n;
	    continue;
	}
	if(last!=n)
	    map[n-1][n]=map[n][n-1]=Dis(n-1,n)/v1;
	n++;
    }
    n--;
    for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	    map[i][j]=min(map[i][j],Dis(i,j)/v2);
    printf("%.0f\n",Distra(1,n));
    return 0;
}