poj 2502 Suwbay【floyd】

我就是我 2022-08-09 18:38 17阅读 0赞

Subway

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 7556</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 2461</td> 
  </tr> 
 </tbody> 
</table>

题目大意：给你两个坐标，分别是家的坐标和学校的坐标，接下来每行给出一条地铁的线路【即地铁的起点站的坐标，经过的站点的坐标，终点站的坐标】【地铁路线最多不超过200条】，已知人步行速度为10km/h，地铁速度为40km/h【注意单位】，要求输出加到学校最少花几分钟？【地铁线路是双向的】

思路：把每个坐标当成一个图中的点，把每个站点间所需要花费的时间当做权值，地铁各站之间的权值为两站点的直线距离除以地铁的速度，除此之外，其他出现过的点的权值为距离除以人步行的速度，然后就是最短路径的模板了；【只要把边权储存的恰当，那么剩下的就简单】

已Accept代码【c++提交】：

#include <cstdio>
    #include <cmath>
    #include <algorithm>
    #define walk_v (10000.0 / 60.0)		//步行速度 
    #define car_v (40000.0 / 60.0)		//地铁速度 
    #define INF 1.0e15					//无穷大 
    using namespace std;
    
    int n;
    const int maxn = 202;
    double map[maxn][maxn];
    
    struct Point {
    	double x, y;
    }p[maxn];
    
    double Dis_a_to_b(int i, int j, double v) {		//计算两点间近距离 
    	return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)) / v;
    }
    
    int main() {
    	for(int i = 0; i < maxn; i++)
    		for(int j = 0; j < maxn; j++)
    			map[i][j] = i == j ? 0 : -1; 
    	scanf("%lf%lf%lf%lf", &p[0].x, &p[0].y, &p[1].x, &p[1].y);
    	n = 2;
    	double pre_x = -1;
    	while(scanf("%lf%lf", &p[n].x, &p[n].y) == 2) {
    		if(pre_x != -1 && p[n].x !=-1)
    			map[n][n - 1] = map[n -1][n] = Dis_a_to_b(n - 1, n, car_v);		//先记录地铁各站点得权值 
    		pre_x = p[n].x;
    		if(p[n].x != -1)
    			n++;
    	}
    	for(int i = 0; i < n; i++)
    		for(int j = i + 1; j < n; j++)
    			if(map[i][j] == -1)
    				map[i][j] = map[j][i] = Dis_a_to_b(i, j, walk_v);			//两点间没有地铁相通 
    	//floyd  
    	for(int k = 0; k < n; k++)
    		for(int i = 0; i < n; i++)
    			for(int j = 0; j < n; j++)
    				if(map[i][k] != -1 && map[k][j] != -1)					//如果map[i][j] == -1; 表示该站点没出现过 
    					map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
    	printf("%.0lf\n", map[0][1]);
    	return 0;
    }