。。。A*是个啥都不知道。。
果然是s==t的问题……加个if(s==t) k++就A了……
| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 20437 | Accepted: 5572 |
Description
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.
Input
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
Sample Input
2 2
1 2 5
2 1 4
1 2 2
Sample Output
14
Source
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
#define maxn 100005
int n, m, s, t, k ,id;
int vis[maxn], d[maxn], head[maxn],tail[maxn];
struct Edge{
int u, v, c, next, last;
Edge(){}
Edge(int u, int v, int c) :u(u), v(v), c(c){}
}p[maxn];
void add(int u, int v, int c){
p[id] = Edge(u, v, c);
p[id].next = head[u]; p[id].last = tail[v];
head[u] = id; tail[v] = id++;
}
struct node{
int u, c;
bool operator<(const node& rmh)const{
return d[u]+c>d[rmh.u]+rmh.c;
}
};
void dij(int t){
priority_queue<node>q;
memset(vis, , sizeof vis);
for (int i = ; i <= n; i++)d[i] = INF;
d[t] = ; q.push(node{ t, });
while (!q.empty()){
node x = q.top(); q.pop();
int u = x.u;
if (vis[u])continue;
vis[u] = ;
for (int i = tail[u]; i + ; i = p[i].last){
int v = p[i].u;
if (d[v] > d[u] + p[i].c){
d[v] = d[u] + p[i].c;
q.push(node{ v, });
}
}
}
}
int astar(int s){
priority_queue<node>q;
while (!q.empty())q.pop();
q.push(node{ s, });
while (!q.empty()){
node x = q.top(); q.pop();
int u = x.u;
if (u == t){
if (k)k--;
else return x.c;
}
for (int i = head[u]; i + ; i = p[i].next)
q.push(node{ p[i].v, x.c+p[i].c });
}
return -;
}
void init(){
id = ;
memset(head, -, sizeof head);
memset(tail, -, sizeof tail);
}
int main(){
while (~scanf("%d%d", &n, &m)){
init();
for (int i = ; i < m; i++){
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
add(u, v, c);
}
scanf("%d%d%d", &s, &t, &k);
dij(t);
if (d[s] == INF){ printf("-1\n"); continue; }
if (s != t)k--;
printf("%d\n",astar(s));
}
return ;
}
启发式搜索，如果直接搜相当于爆搜出所有的从s到t的路径，记录然后排序，找k短。。。不管是内存，还是时间都会爆。。。
不过不知道为什么这么启发式是对的。。。
f(n)=g(n)+h(n);用优先队列每次出队最小f(n)
g(n)从s点来到当前点n的距离
h(n)从n到t的最短距离。。。用dijkstra
然后t出队k次时的当前点t的路径就是k短了。如果队空，就没有k短那么多了。。。输出-1
A*+最短路为什么是正确的。。。
可以这么想
假如某个点出队了k次也就是不同或相同的路径经过这个点k次了，那么从这个点走最短路到t肯定算k短，因为之前的k-1次都比这次短而且，还没有找到其他的k短。。
因为A*+最短路的这种思路是对的。。所以A*的方法也是对的。。。
再贴一段别人的看法
首先讲讲A*算法吧。众所周知，A*算法就是启发式搜索，基本形式就是这样:f(x)=g(x)+h(x);其中f(x)代表在x点所需要的总代价，而g(x)代表：从源点到x点已经耗费的实际代价，h(x)代表从x到终点需要的估计代价，这个函数是一个估计值.而从x到终点真正需要的代价为h*(x)，在整个启发式搜索中我们必须保证h(x)<=h*(x);不然的话会由于对当前的估价值过高，则会引起答案的错误。构建A*的关键在于准确的规划一个h(x)函数，使得接近h*(x),这样的搜索会使得答案又快又准。可以想象h(x)过小会使得解空间过大，这样搜索出来的结果会很准确但是速度太慢，而对h(x)的过高估计，即估计代价太大会使得结果不准确。
这样我们可以理解了BFS的搜索过程，BFS的搜索过程中没有考虑到h(x)的估计代价，也就是说h(x)=0,只考虑g(x)的实际代价。这样根据实际代价来进行搜索，虽然可以说是很恶心的A*,同样地我们可以知道，BFS的解空间确实很大。
第一次写A*,目前只会应用在K短路上。不过也有点感觉了，关键在于h(x)的设计！
谈具体的实现：
首先我们在解空间取出的就是f(x)最小的，这样我们就要运用到优先队列了。这里提供一个使用C++系统优先队列的方法：
- #include<queue>
- struct Q{
- int g,h;
- bool operator<( Q a )const
- { return a.g+a.h<g+h; }
- }
- priority_queue<Q>queue;
- Q b;
- queue.push(b);
C++的STL中自带了优先队列，通过重载运算法"<",可以实现我们需要的对f(x)的自动维护。
描述一下怎样用启发式搜索来解决K短路。
首先我们知道A*的基础公式：f(x)=g(x)+h(x);对h(x)进行设计，根据定义h(x)为当前的x点到目标点t所需要的实际距离。也就是说x->t距离，由于有很多的节点都是到t的距离，为了计算这个估计值，当然必须先算出x->t的最短路径长度。显然x的值很多而t的值只有一个，对每个x去求单源点最短路径当然不划算！于是反过来做，从t点出发到其他点的单源点最短路径，这样吧估价函数h(x)都求出来，注意这样求出来的h(x)=h*(x);不可能x到t更短了。。。所以h(x)<=h*(x)在这里等于h*(x);
然后就可以对构造完的h(x)开始启发式搜索了。
首先的点当然就是定义头结点了，头结点的已消耗代价为0,估计代价为h[s],下一个点为v;进入队列，开始for循环。每次取出队头的f(x)最小的节点对其他节点进行拓展。对当前节点的拓展次数++，若当前节点的拓展次数超过K,显然不符合要求，则不进行拓展其实在k之前就会找到答案了。若对t节点的拓展次数恰好为K,则找到了所需要的。对当前节点的拓展次数即为到当前节点的第几短路。找到需要节点的K短路后，返回g(t)即可，也就是通过K次拓展的实际消耗的长度。
在for循环中的入队情况：当前节点的可拓展所有边，的所有状态都入队，当前节点到拓展节点的实际代价为当前节点的实际代价+两节点之间的边长。下个节点就是拓展节点，估计函数的值则为拓展节点到目标节点的距离h(x);
随机推荐
-
Gradle 使用本地的Jar包（gradle oracle ojdbc14 ）
Gradle 使用本地的Jar包(gradle oracle ojdbc14 ) 因为Oracle的驱动包在Maven上是没办法直接下载到的,所以在使用Gradle的使用,会导致无法加载Oracle, ...
-
强连通分量的Tarjan算法
资料参考 Tarjan算法寻找有向图的强连通分量 基于强联通的tarjan算法详解 有向图强连通分量的Tarjan算法 处理SCC(强连通分量问题)的Tarjan算法 强连通分量的三种算法分析 Tar ...
-
Careercup - Google面试题 - 5724823657381888
2014-05-06 06:37 题目链接 原题: Given an array of (unsorted) integers, arrange them such that a < b > ...
-
Json处理函数json_encode json_decode
json_decode — 对 JSON 格式的字符串进行编码 mixed json_decode ( string $json [, bool $assoc = false [, int $dept ...
-
转: JS自定义事件的定义和触发(createEvent, dispatchEvent)
四.伪DOM自定义事件 这里的“伪DOM自定义事件”是自己定义的一个名词,用来区分DOM自定义事件的.例如jQuery库,其是基于包装器(一个包含DOM元素的中间层)扩展事件的,既与DOM相关,又不直 ...
-
JAVA HashMap 解析
1.简介(其实是HashMap注释的大致翻译) 本文基于JDK1.8,与JDK1.7中的HashMap有一些区别,看官注意区别. HashMap实现了Map接口,提供了高效的Key-Value访问.H ...
-
Java经典编程题50道之二十四
有5个人坐在一起,问第5个人多少岁,他说比第4个人大2岁.问第4个人岁数,他说比第3个人大2岁. 问第三个人,他说比第2人大两岁.问第2个人, 说比第一个人大两岁.最后问第一个人,他说是10岁. 请问 ...
- h5解决键盘谈起,输入框失去焦点
-
ionic3.x开发小坑记录（一）
自定义font的时候,在assets中创建的文件夹名字别用fonts,会与ionic默认样式冲突,在浏览器中调试是正常的,到手机上就出问题了. 在html中写img的src直接如图 assets前面 ...
-
奇怪吸引子---ChenLee
奇怪吸引子是混沌学的重要组成理论,用于演化过程的终极状态,具有如下特征:终极性.稳定性.吸引性.吸引子是一个数学概念,描写运动的收敛类型.它是指这样的一个集合,当时间趋于无穷大时,在任何一个有界集上出 ...