A*算法

思路和性质

  1. 在bfs基础上将队列换为优先队列，用(起点到当前点的距离+当前点到终点的估计距离)排序
  2. 估计距离<=实际距离
  3. 数据无解A*比BFS慢，优先队列操作O(logn)
  4. 终点第一次出队一定是答案(可证明)

八数码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

typedef pair<int, string> pis;

string seq, bg, en = "12345678x";
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char dir[] = "urdl";
unordered_map<string, int> dist;  //dist[t]:目前状态t距离初始状态的距离
unordered_map<string, pair<string, char>> pre;   //prev[t]={a, b} :状态t由状态a，朝方向b转移
priority_queue<pis, vector<pis>, greater<pis>> heap;  //{起点到当前状态的距离 + 当前状态到目标的估计距离, 状态}

//估价函数(必须<=真实值)
int f(string st)
{
    int v = 0;
    for (int i = 0; i < 9; i ++ )
        if (st[i] != 'x')
        {
            int num = st[i] - '1';
            v += abs(i / 3 - num / 3) + abs(i % 3 - num % 3);
        }
        
    return v;
}

string astar()
{
    //初始化
    dist[bg] = 0;
    heap.push({f(bg), bg});
    
    while (heap.size())
    {
        auto head = heap.top();
        heap.pop();
        string st = head.second;
        
        //终点第一次出队为最小值
        if (st == en) break;
        
        //找到“x”所在位置
        int x, y;
        for (int i = 0; i < 9; i ++ )
            if (st[i] == 'x')
                x = i / 3, y = i % 3;
        
        string prest = st; //存储当前状态
        //枚举邻点
        for (int i = 0; i < 4; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;  //越界
            swap(st[x * 3 + y], st[nx * 3 + ny]);
            
            //新状态未被更新过 或 由当前状态转移距离更短
            if (dist.count(st) == 0 || dist[prest] + 1 < dist[st])
            {
                dist[st] = dist[prest] + 1;
                pre[st] = {prest, dir[i]};
                heap.push({dist[st] + f(st), st});
            }
            
            swap(st[x * 3 + y], st[nx * 3 + ny]);
        }
    }
    
    string res = "";
    while (en != bg)
    {
        res += pre[en].second;
        en = pre[en].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string c;
    while (cin >> c)
    {
        bg += c;
        if (c != "x") seq += c;
    }
    
    //求序列逆序数，偶数才有解
    int cnt = 0;
    for (int i = 0; i < 9; i ++ )
        for (int j = i; j < 9; j ++ )
            if (seq[i] > seq[j])
                cnt ++ ;
    
    if (cnt % 2) puts("unsolvable");
    else cout << astar() << endl;
    
    return 0;
}

第k短路

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
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

const int N = 1010, M = 200010;

int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

//预处理估价函数dist
void dijkstra()
{
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0, T});

    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = rh[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int astar()
{
    priority_queue<piii, vector<piii>, greater<piii>> heap;
    heap.push({dist[S], {0, S}});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y.y, distance = t.y.x;
        cnt[ver] ++ ;
        if (cnt[T] == K) return distance;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (cnt[j] < K)
                heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
        }
    }

    return -1;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h), memset(rh, -1, sizeof rh);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    scanf("%d%d%d", &S, &T, &K);
    //起点到终点至少要包含一条边
    if (S == T) K ++ ;

    dijkstra();
    printf("%d\n", astar());

    return 0;
}