题目
二维平面上有n个点，每个点的横纵坐标均为非负整数。两个点之间的距离记为 min(abs(x1 - x2), abs(y1 - y2))，求从点1到达点n的最短路径长度。
比较容易想到使用最短路径算法来解决，但关键的问题是如何建图！参考了网上的代码http://blog.csdn.net/chenzhenyu123456/article/details/50650029
实现
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
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<SpNode, vector<SpNode>, 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
", result);
return 0;
}