POJ - 2449 Remmarguts' Date

Posted on | In ,

关于A*

A*算法是一种启发式搜索的算法，通过设定合理的估价函数，我们能够减少不必要的搜索从而达到减低时间复杂度的目的。当我们计算A*算法时，我们维护一个优先队列，同时按照我们规定的估价函数来进行排序。我们这样定义一个估价函数：F=G+H。这里：
F：需要排序的估价函数值
G：从起点到当前点的花费
H：我们人为设定的估价函数值
在这里我们这样理解这个估价函数，我们从起点到终点，我们定义H为当前点到终点的距离，很显然根据G+H，绕路走的F是比较大的，F就是我们人为观感上的“绕路走”，A*的估价函数的意义就是少“绕路走”，同时我们常常使用的BFS就是没有估价函数的，所以即便一些步骤我们明明知道不会产生最优解，我们依然遍历了这些步骤，A*的估价函数则避免了这个问题。

思路

本题我们先用dijkstra计算t到每个点的距离，然后这个距离就是我们的估价函数，然后我们从s出发使用A*，然后等第k次出队列碰到t点我们输出距离。需要注意的是当s==t时k++，因为题目要求必须要走一条路。

参考

A*算法入门

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int MAXN=1005,MAXM=100005;
int n,m,s,t,k;
struct cmp{
    bool operator ()(pair<int,int> p1,pair<int,int> p2){
        if(p1.first!=p2.first)return p1.first<p2.first;
        else return p1.second<p2.second;
    }
};
struct A{
    int f,g,v;
    A(){};
    A(int f,int g,int v):f(f),g(g),v(v){};
    bool operator <(const A a)const{
        if(a.f==f)return a.g<g;
        else return a.f<f;
    }
};
int dist[MAXN];
vector<pair<int,int> > G[MAXN],H[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> pq;
void dijkstra(int V){
    for(int i=0;i<MAXN;i++)dist[i]=INF;
    dist[V]=0;
    pq.push(make_pair(0,V));
    while(!pq.empty()){
        pair<int,int> temp=pq.top();
        pq.pop();
        int val=temp.first,pos=temp.second;
        if(val>dist[pos])continue;
        for(vector<pair<int,int> >::iterator it=G[pos].begin();it!=G[pos].end();it++){
            if(dist[it->first]>dist[pos]+it->second){
                dist[it->first]=dist[pos]+it->second;
                pq.push(make_pair(dist[it->first],it->first));
            }
        }
    }
}
priority_queue<A> p;
int aStar(int from,int to){
    int cnt=0;
    while(!p.empty())p.pop();
    if(from==to)k++;
    if(dist[from]==INF)return -1;
    A t(dist[from],0,from);
    p.push(t);
    while(!p.empty()){
        A temp=p.top();
        p.pop();
        if(temp.v==to){
            cnt++;
            if(cnt==k)return temp.g;
        }
        for(vector<pair<int,int> >::iterator it=H[temp.v].begin();it!=H[temp.v].end();it++){
            A te(temp.g+it->second+dist[it->first],temp.g+it->second,it->first);
            p.push(te);
        }
    }
    return -1;
}

int main() {
    int u,v,w;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            G[v].push_back(make_pair(u,w));
            H[u].push_back(make_pair(v,w));
        }
        scanf("%d%d%d",&s,&t,&k);
        dijkstra(t);
        printf("%d\n",aStar(s,t));
        for(int i=0;i<MAXN;i++)G[i].clear(),H[i].clear();
    }
	return 0;
}