1 条题解
-
0
解题思路:
- 数据建模:把家、学校和各个地铁站当作图的节点,节点间的边权代表从一个节点到另一个节点所需的时间。
- 边权计算:步行速度为10千米 / 小时,地铁速度为40千米 / 小时。同一条地铁线路上相邻站点的时间按地铁速度算,其他情况按步行速度算。
- 最短路径求解:运用迪杰斯特拉算法找出从家到学校的最短时间路径。
代码
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<math.h> using namespace std; const int N = 300; const int INF = 9999999; double map[N][N]; double num[N]; int v[N]; int n,m; struct node { int x,y; }q[10001]; void dijkstra() { for(int i=0;i<n;i++) { num[i] = map[0][i]; v[i] = 0; } num[0] = 0; for(int i=0;i<n;i++) { int min = INF,k; for(int j=0;j<n;j++) { if(v[j] == 0 && num[j]<min) { min = num[j]; k = j; } } if(min == INF) { break; } v[k] = 1; for(int j=0;j<n;j++) { if(v[j] == 0 && num[j] > num[k] + map[k][j]) { num[j] = num[k] + map[j][k]; } } } printf("%.0lf\n",num[1]); } int main() { while(cin >> q[0].x >> q[0].y >> q[1].x >> q[1].y) { for(int i=0;i<N;i++) { for(int j=0;j<=N;j++) { map[i][j] = INF; } map[i][i] = 0; } n = m = 2; while(cin >> q[n].x >> q[n].y) { if(q[n].x == -1 && q[n].y == -1) { m = n; continue; } if(n!=m) { double d = sqrt((double)(q[n].y-q[n-1].y)*(q[n].y - q[n-1].y) + (q[n].x - q[n-1].x)*(q[n].x - q[n-1].x)); d = 3*d/2000; map[n][n-1] = d; map[n-1][n] = d; } n++; } for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(map[i][j] == INF) { double d = sqrt((double)(q[j].y-q[i].y)*(q[j].y - q[i].y) + (q[j].x - q[i].x)*(q[j].x - q[i].x)); d = 3*d/500; map[i][j] = d; map[j][i] = d; } } } dijkstra(); } return 0; }
- 1
信息
- ID
- 1503
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者