本文共 3254 字，大约阅读时间需要 10 分钟。
二维平面上有n个点，每个点的横纵坐标均为非负整数。两个点之间的距离记为 min(abs(x1 - x2), abs(y1 - y2))，求从点1到达点n的最短路径长度。
比较容易想到使用最短路径算法来解决，但关键的问题是如何建图！参考了网上的代码
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int kMaxNodes = 100005;//节点结构体，用于记录点的横纵坐标，以及序号struct Node{ int x; int y; int id;};Node gNodes[kMaxNodes];//对节点按照横坐标进行排序，比较函数bool Cmp1(const Node& node1, const Node& node2){ if (node1.x == node2.x) return node1.y < node2.y; return node1.x < node2.x;}//对节点按照纵坐标进行排序，比较函数bool Cmp2(const Node& node1, const Node& node2){ if (node1.y == node2.y) return node1.x < node2.x; return node1.y < node2.y;}//边结构体，用于构建图struct Edge{ int to; int dist; int next;};//求最短路的节点结构体，id表示点的序号，dist为从源点到达该点的最短距离struct SpNode{ int id; int dist; SpNode(int i = 0, int d = 0) :id(i), dist(d){};};//比较函数，用于dijkstra中对源点到点的排序struct Cmp{ bool operator()(const SpNode& node1, const SpNode& node2){ return node1.dist > node2.dist; }};Edge gEdges[4 * kMaxNodes];int gEdgeIndex;int gHead[kMaxNodes];bool gVisited[kMaxNodes];int gMinDist[kMaxNodes]; //记录从源点到达点的最短距离void Init(){ gEdgeIndex = 0; memset(gEdges, -1, sizeof(gEdges)); memset(gHead, -1, sizeof(gHead)); memset(gVisited, false, sizeof(gVisited)); memset(gMinDist, -1, sizeof(gMinDist));}void InsertEdge(int u, int v, int d){ int e = gEdgeIndex++; gEdges[e].to = v; gEdges[e].dist = d; gEdges[e].next = gHead[u]; gHead[u] = e;}int Dijkstra(int n){ priority_queue , Cmp> pq; SpNode node; node.id = 0; gMinDist[0] = node.dist = 0; pq.push(node); while (!pq.empty()){ node = pq.top(); pq.pop(); int u = node.id; if (gVisited[u]) continue; gVisited[u] = true; if (u == n-1) break; for (int e = gHead[u]; e != -1; e = gEdges[e].next){ int v = gEdges[e].to; if (gMinDist[v] == -1 || gMinDist[v] > gMinDist[u] + gEdges[e].dist){ gMinDist[v] = gMinDist[u] + gEdges[e].dist; pq.push(SpNode(v, gMinDist[v])); } } } return gMinDist[n-1];}int main(){ int n, x, y; Init(); scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d %d", &gNodes[i].x, &gNodes[i].y); gNodes[i].id = i; } //建图 /* 先对所有点的横坐标进行排序，有些点的横坐标相同，则将这些点浓缩成一个点，同时选择这些点中id最小的作为该集合的代表。 集合内的各个点和代表点之间添加长度为0的边； 集合的代表点之间添加边，边的长度为点的横坐标的差值，但是并不需要所有的代表点之间都添加边，只需要在相邻的集合之间添加边。 因为如果 i，j，k分别为三个集合的代表点，i和j相邻，j和k相邻，从i到k的路径等于从i到j的路径和从j到k的路径之和（如果单看横坐标）。 在用dijkstra算法求最短路径的时候只通过i到j，j到k即可，不需要额外添加i到k的边了。 同样，对所有点按照纵坐标进行排序.....添加边 最后，在构造完成的图上运用dijkstra算法求最短路径即可。 */ sort(gNodes, gNodes + n, Cmp1); int i = 0, j; while (i < n-1){ j = i + 1; while (gNodes[i].x == gNodes[j].x){ InsertEdge(gNodes[i].id, gNodes[j].id, 0); InsertEdge(gNodes[j].id, gNodes[i].id, 0); j++; } if (j >= n) break; InsertEdge(gNodes[i].id, gNodes[j].id, gNodes[j].x - gNodes[i].x); InsertEdge(gNodes[j].id, gNodes[i].id, gNodes[j].x - gNodes[i].x); i = j; } i = 0; sort(gNodes, gNodes + n, Cmp2); while (i < n-1){ j = i + 1; while (gNodes[i].y == gNodes[j].y){ InsertEdge(gNodes[i].id, gNodes[j].id, 0); InsertEdge(gNodes[j].id, gNodes[i].id, 0); j++; } if (j >= n) break; InsertEdge(gNodes[i].id, gNodes[j].id, gNodes[j].y - gNodes[i].y); InsertEdge(gNodes[j].id, gNodes[i].id, gNodes[j].y - gNodes[i].y); i = j; } int result = Dijkstra(n); printf("%d\n", result); return 0;}
转载地址：http://wdwsl.baihongyu.com/