2017计算机学科夏令营上机考试H:Subway（图的构建+Dijkstra）
发布时间
阅读量：
阅读量
题目大意
给定起点和终点，以及任意条地铁线路，任意站点之间可以选择步行或乘坐地铁（如果两站在同一条地铁线上），步行速度10km/h，地铁速度40km/h，要求从起点到终点所花时间最短。
思路分析
本题也是图的最短路径问题，只不过此处的路径应该用所花时间来表示，用邻接矩阵存储图的信息。因而本题难度在于图的构建 部分。
- 初始化，将所有站点间距离设为无穷大INF(double类型可设为“1e30”)；
- 计算每条地铁线各站点间，乘坐地铁所需要花费的时间，存入邻接矩阵中；
- 计算包含起点、终点在内的所有点间，步行所需要花费的时间，与邻接矩阵中已有时间相比较，取较小值存入矩阵当中。
图构建完毕之后，采用Dijkstra算法，计算出起点至终点的最短距离即可，最后输出的是终点距离d[1]！！！！（我zz。。。一直以为是最后一个结点是终点。。查了好久的错。。。。）
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 210;
const double INF = 1e30;
struct Node
{
double x, y;
}node[maxn];
double map[maxn][maxn];
bool vis[maxn];
double d[maxn];
vector<int> s;
double v1 = 10000.0 / 60.0;
double v2 = 40000.0 / 60.0;
void init()
{
fill(map[0], map[0]+maxn*maxn, INF);
fill(vis, vis+maxn, false);
fill(d, d+maxn, INF);
s.clear();
}
double dis1(Node a, Node b) // 步行时长
{
double len = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
double dis = len / v1;
return dis;
}
double dis2(Node a, Node b) // 地铁时长
{
double len = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
double dis = len / v2;
return dis;
}
void Dijkstra(int start, int n)
{
d[start] = 0.0;
for(int i=0; i<n; i++)
{
int u = -1;
double min_ = INF;
for(int j=0; j<n; j++)
{
if(vis[j]==false && d[j]<min_)
{
u = j;
min_ = d[j];
}
}
if(u == -1)
{
return ;
}
vis[u] = true;
for(int v=0; v<n; v++)
{
if(vis[v]==false && map[u][v]!=INF && d[u]+map[u][v]<d[v])
{
d[v] = d[u] + map[u][v];
}
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
scanf("%lf %lf %lf %lf", &node[0].x, &node[0].y, &node[1].x, &node[1].y);
init();
int cnt = 2;
double x, y;
while(scanf("%lf %lf", &x, &y) != EOF)
{
if(x!=-1 && y!=-1)
{
node[cnt].x = x;
node[cnt].y = y;
s.push_back(cnt);
cnt++;
}
else
{
for(int i=0; i<s.size()-1; i++)
{
map[s[i]][s[i+1]] = map[s[i+1]][s[i]] = dis2(node[s[i]], node[s[i+1]]);
}
s.clear();
}
}
for(int i=0; i<cnt; i++)
{
for(int j=0; j<=i; j++)
{
if(i == j)
{
map[i][j] = INF;
}
else
{
map[i][j] = map[j][i] = min(map[i][j], dis1(node[i], node[j]));
}
}
}
Dijkstra(0, cnt);
printf("%.0lf", d[1]); // 终点距离
fclose(stdin);
return 0;
}全部评论 (0)
还没有任何评论哟~