Subway

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 16322 Accepted: 5207

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

题目大意：给出你的起点坐标和终点坐标，你有两种选择，第一种是步行速度：10km/h，第二种乘地铁：41km/h，现在又一些地铁站，你可以随意上。下地铁，问从起点到终点最短时间是多少分钟？
思路：建图可以说是很恶心了，看了bin巨的代码写的，思路很简单，建图后跑一遍dijkstra然后输出就行了，关键是建图，可以把每个地铁站看作一个顶点，然后用矩阵存距离（因为地铁站最多300个，矩阵完全足够了），每条地铁站求完距离后转化单位，因为题目要求的是分钟，题目给的是km/h，地铁站相邻之间是40Km/h，然后其他任一站时间是10/h，（这是他步行速度，因为他可以任意上下车，也就是说他完全可以从起点走路去终点，用他的步行速度，根据这个我们可以给所有地铁站建边以他的步行速度），代码：

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

const int maxn=300;
const double inf=1e30;

struct Node{
	double x,y;
}node[maxn];
double w[maxn][maxn];
double dis[maxn];
bool vis[maxn];

void dijkstra(int s,int n){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)dis[i]=w[s][i];
	dis[s]=0;
	for(int p=1;p<=n-1;p++){
		double minn=inf;
		int k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]<minn){
				minn=dis[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]>dis[k]+w[k][i]){
				dis[i]=dis[k]+w[k][i];
			}
		}
	}
} 
double distance11(Node a,Node b){
	return (double)sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
	while(scanf("%lf%lf%lf%lf",&node[1].x,&node[1].y,&node[2].x,&node[2].y)!=EOF){
		int cnt1=3;
		int x,y;
		int n=2;
		for(int i=1;i<=300;i++){
			for(int j=1;j<=300;j++){
				if(i==j)w[i][j]=0;
				else w[i][j]=inf;
			}
		}
		
		while(scanf("%d%d",&x,&y)!=EOF){
			if(x==-1&&y==-1){
				cnt1=n+1;
				continue;
			}
			n++;
			node[n].x=x;
			node[n].y=y;
			if(n!=cnt1)w[n][n-1]=w[n-1][n]=min(w[n][n-1],distance11(node[n],node[n-1])/(double)(40000.0/60.0));
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				w[i][j]=min(w[i][j],distance11(node[i],node[j])/(double)(10000.0/60.0));
			}
		}
		dijkstra(1,n);
	    printf("%.0lf\n",(dis[2]));
	}
}