赞
踩
题目要求我们求出最短路径,那么要考虑的第一个问题:我们是使用有权图还是无权图呢——想到要计算逃脱跳数,因此我采用了有权图,将边的权重记为1。
第二个问题,是选择单源最短路径算法还是多源最短路径算法呢?
因为可以理解为从固定点(湖心)开始逃脱,因此我采用的是单源最短路径算法,也就是Dijkstra算法。
大致的解题思路是:
①将dist值由小到大遍历,找出逃脱时最小的dist值。
(注意:此时的dist值比逃脱跳数小1,因为dist值计算的是从源点到目标点的最短距离,而此处的目标的是上岸前的最后一个节点。)
②由于可能会存在多条最短逃脱路径,按照题目说明:
如果有很多最短的路径,只需输出第一次跳跃最少的路径,这保证是唯一的。
因此,我们就要比较这些路径里,第一跳距离最短的那一条。
101
,而不是100
dist[]
数组的初始化:
dist
值被初始化为0dist
值被初始化为它们的边的权重dist
值被初始化为∞
path[]
数组的初始化:
path
值初始化为-1path
值被初始化为原点的下标path
值均被初始化为-1#include <stack> #include <cmath> #include <cstdlib> #include <iostream> #define MAXSIZE 101 #define INFINITY 65535 #define ERROR 65535 int D; typedef int weightType; typedef int vertex; /* 坐标结构体 */ struct pos { int x, y; }; /* 边节点 */ struct ENode { vertex V1, V2; weightType weight; }; typedef ENode* ptrToENode; typedef ptrToENode Edge; /* 图节点 */ struct GNode { int Nv; int Ne; weightType G[MAXSIZE][MAXSIZE]; //邻接矩阵 pos data[MAXSIZE]; //存顶点的坐标 }; typedef GNode* ptrToGNode; typedef ptrToGNode MGraph; MGraph creatGraph(int Nv) { MGraph G = (MGraph)malloc(sizeof(GNode)); G->Nv = Nv; /* 初始化邻接矩阵 */ for (vertex i = 0; i < G->Nv; i++) { for (vertex j = 0; j < G->Nv; j++) { G->G[i][j] = INFINITY; } } return G; } void InsertEdge(MGraph Graph, Edge E) { /* 插入边 (V1, V2) */ Graph->G[E->V1][E->V2] = E->weight; Graph->G[E->V2][E->V1] = E->weight; Graph->Ne++; } MGraph buildGraph() { int Nv; std::cin >> Nv >> D; /* 建立有Nv+1个顶点但没有边的图 */ MGraph G = creatGraph(Nv + 1); /* 保存每个顶点所在的位置坐标 */ G->data[0] = { 0,0 }; for (int i = 1; i < G->Nv; i++) { std::cin >> G->data[i].x >> G->data[i].y; } /* 建立边 */ Edge E = (Edge)malloc(sizeof(ENode)); for (vertex i = 0; i < G->Nv; i++) { for (vertex j = 0; j < G->Nv; j++) { if (i == j) G->G[i][j] = 0; else if (i == 0) { double d = sqrt(pow(G->data[i].x - G->data[j].x, 2) + pow(G->data[i].y - G->data[j].y, 2)) - 7.5; if (d < D) { E->V1 = i; E->V2 = j; E->weight = 1; InsertEdge(G, E); } } else { double d = sqrt(pow(G->data[i].x - G->data[j].x, 2) + pow(G->data[i].y - G->data[j].y, 2)); if(d <= D) { E->V1 = i; E->V2 = j; E->weight = 1; InsertEdge(G, E); } } } } return G; } vertex findMinDist(MGraph Graph, int dist[], bool collected[]) { vertex V, minV; int minDist = INFINITY; for (V = 0; V < Graph->Nv; V++) { if (collected[V] == false && dist[V] < minDist) { minDist = dist[V]; minV = V; } } if (minDist < INFINITY) return minV; else return ERROR; //错误标记 } bool Dijkstra(MGraph Graph, int dist[], int path[], vertex S) { bool collected[MAXSIZE]; vertex V, W; /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */ for (V = 0; V < Graph->Nv; V++) { dist[V] = Graph->G[S][V]; if (S == V) { path[V] = -1; } else if (dist[V] < INFINITY ) path[V] = S; else path[V] = -1; collected[V] = false; } /* 将起点收入集合 */ dist[S] = 0; collected[S] = true; while (1) { /* V = 未被收录顶点中dist最小者 */ V = findMinDist(Graph, dist, collected); if (V == ERROR) break; collected[V] = true; /* 遍历图中所有顶点 */ for (W = 0; W < Graph->Nv; W++) { /* 若为V的邻接点且未被访问过 */ if (collected[W] == false && Graph->G[V][W] != INFINITY) { if (dist[V] + Graph->G[V][W] < dist[W]) { dist[W] = dist[V] + Graph->G[V][W]; //更新dist[W] path[W] = V; //更新S到W的路径 } } } } return true; } bool live(MGraph Graph, vertex V) { /* 检查能否上岸*/ int X = Graph->data[V].x; int Y = Graph->data[V].y; if (abs(50 - X) <= D || abs(50 - Y) <= D || abs(-50 - X) <= D || abs(-50 - Y) <= D) return true; return false; } void clearStack(std::stack<vertex>& s) { while (!s.empty()) s.pop(); } int main() { int path[MAXSIZE]; int dist[MAXSIZE]; std::stack<vertex> liveStack; //当有多条最小路径,存储每条路径的最终点 MGraph Graph = buildGraph(); /* 判断能否一步上岸 */ if (abs(50 - 7.5) <= D) { std::cout << 1; return 0; } Dijkstra(Graph, dist, path, 0); //0是起始点的数组下标 /* 将dist值由小到大遍历,找出逃脱时最小的dist值,即逃脱跳数 */ int minDist = INFINITY; for (vertex V = 0; V < Graph->Nv; V++) { if (live(Graph, V)) { if (dist[V] < minDist) { clearStack(liveStack); minDist = dist[V]; liveStack.push(V); } /* 保存dist相同的逃脱路径的最终节点 */ else if (dist[V] == minDist) { minDist = dist[V]; liveStack.push(V); } } } if (minDist == INFINITY) std::cout << '0'; /* 无多条最短路径 */ else if (liveStack.size() == 1) { std::stack<vertex> s; vertex e = liveStack.top(); std::cout << dist[e] + 1 << std::endl; //输出跳数 s.push(liveStack.top()); while (path[e] != 0) { s.push(path[e]); e = path[e]; } while (!s.empty()) { vertex top = s.top(); s.pop(); if (s.empty()) std::cout << Graph->data[top].x << ' ' << Graph->data[top].y; else std::cout << Graph->data[top].x << ' ' << Graph->data[top].y << std::endl; } } /* 找出第一跳最短的逃脱路径 */ else { vertex S, E, minS, minE; double minDist = INFINITY; /* 遍历每条最短路径 */ minS = minE = liveStack.top(); while (!liveStack.empty()) { S = E = liveStack.top(); liveStack.pop(); /* 首先找到每条路径的鳄鱼起点 */ while (path[S] != 0) S = path[S]; /* 找出第一跳最短的那个距离以及顶点 */ if (sqrt(pow(Graph->data[S].x, 2) + pow(Graph->data[S].y, 2)) < minDist) { minDist = sqrt(pow(Graph->data[S].x, 2) + pow(Graph->data[S].y, 2)); minS = S; minE = E; } } /* 输出结果 */ std::stack<vertex> res; std::cout << dist[minE] + 1 << std::endl; //输出跳数 res.push(minE); while (path[minE] != 0) { res.push(path[minE]); minE = path[minE]; } while (!res.empty()) { vertex top = res.top(); res.pop(); if (res.empty()) std::cout << Graph->data[top].x << ' ' << Graph->data[top].y; else std::cout << Graph->data[top].x << ' ' << Graph->data[top].y << std::endl; } } return 0; }
前两天一直没做出来题,因为自己又陷入了形式主义的怪圈,把学习任务当成了一种打卡,觉得我完成了就够了,但是没有真正掌握知识,所以没那么复杂的题自己会卡特别久。
感谢我的女朋友,她让我意识到了自己的问题。我现在也认识到,学习是为了真正地去掌握知识,而不是为了赶DDL。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。