【概述】
A*（A-Star）算法是一种在静态路网中，求解最短路的最有效的直接搜索方法，也是解决许多搜索问题的有效算法之一。
A* 算法实际上是对 Dijkstra 算法的优化后得到的，关于 Dijkstra 算法：点击这里
A*算法在程序设计竞赛中，一般用于解决 k 短路问题，关于 k 短路问题：点击这里
【原理】
在 Dijkstra 算法中，我们借助优先队列来实现，每次从优先队列中取出结点，再从这个结点扩散到其他结点，而优先队列的优先依据是根据起点到队列中结点最近的一个，即队列中的结点离起始点最近的会先出队。
但不可避免的是，Dijkstra 存在跑偏问题，如下图，若起点为 1 号点，终点为 6 号点，首先一定会走 3、4 号点，这肯定不是最佳路径，一开始就跑偏了。
在 Dijkstra 算法中，判断的依据只是已知的起点到某点 i 的距离 G(i)，那么我们可以增加一个判断量来减少跑偏的概率。
如果能够计算当前点 i 到终点的距离，再结合 G(i)，那么可以防止过度跑偏，但这个距离是未知的，因此我们可以设置一个估值，即启发函数 H(i)。
启发函数 H(i) 的设置是 A* 算法关键，如何设置这个启发函数影响到算法的性能，在得到了启发函数后，我们就有了最终的估价函数 F(i)=G(i)+H(i)，在优先队列中，以这个估价函数作为指标进行出队。
一般来说，在二维平面图中，我们将图置于坐标轴中，通过计算结点间的欧几里得距离来得到两点间的直线距离，这个距离即可作为当前点 i 到终点距离的估值。但欧几里得距离的计算要进行开方，较为复杂，一般通过加减法来计算简单的曼哈顿距离来代替欧几里得距离，作为启发函数 H(i)。
而在一般图中，我们通常是建立反图，跑一次最短路算法，将得到每个点到 t的最短路的距离 dis[i] 作为启发函数 H(i)
【实现】
struct Edge {int to, next;int w;Edge() {}Edge(int to, int next, int w) : to(to), next(next), w(w) {}};struct Map {int tot;int head[N];Edge edge[N * N];Map() {tot = 0;memset(head, -1, sizeof(head));}void addEdge(int x, int y, int w) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].w = w;head[x] = tot;}Edge &operator[](int pos) { return edge[pos]; }};int n, m;Map G, GT;int dis[N];bool vis[N];struct Status{int node;//点编号int diss;//距离int priority;//优先级Status() : node(0), diss(0), priority(dis[0]) {}Status(int node, int diss) : node(node), diss(diss), priority(diss + dis[node]) {}bool operator<(Status b) const { return priority > b.priority; }} status;bool SPFA(int S, int T) { //对反图求最短路memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));dis[S] = 0;queue<int> Q;Q.push(S);while (!Q.empty()) {int x = Q.front();Q.pop();vis[x] = false;for (int i = GT.head[x]; i != -1; i = GT[i].next) {int y = GT[i].to;if (dis[x] + GT[i].w < dis[y]) {dis[y] = dis[x] + GT[i].w;if (!vis[y]) {Q.push(y);vis[y] = true;}}}}return dis[T] != INF;}int AStar(int S, int T) {priority_queue<Status> Q;Q.push(Status(S, 0));while (!Q.empty()) {Status temp = Q.top();Q.pop();if (temp.node == T)return temp.diss;for (int i = G.head[temp.node]; i != -1; i = G[i].next)if (temp.diss + G[i].w < temp.diss)Q.push(Status(G[i].to, temp.diss + G[i].w));}return -1;}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y, w;scanf("%d%d%d", &x, &y, &w);G.addEdge(x, y, w);GT.addEdge(y, x, w);}int s, t;scanf("%d%d", &s, &t);if (!SPFA(t, s))printf("-1\n");elseprintf("%d\n", AStar(s, t));return 0;}
