题前闲话

先骂一下自己每次都把解题报告写成做题笔记

【Coel.解题报告】【新的生活开始】 [SCOI2007]k短路

选科调整完成了，虽然没有重新分到实验班，但至少调好了，以后还是有奔头的。继续努力学习吧，文化课和竞赛都不能落下w！

题目简介

特别注意：本随笔使用的A*算法并不是解决K短路问题的正解，正确解法应当参考次短路算法进行扩展，或者使用可持久化可并堆优化。本随笔仅用于学习A*算法的参考。洛谷传送门

题目描述

有 (n) 个城市和 (m) 条单向道路，城市编号为 (1) 到 (n)。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此 (n) 和 (m) 满足(m le n(n-1))。给定两个城市 (a) 和 (b)，可以给 (a) 到 (b) 的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出 (a) 到 (b) 的第 (k) 短路。

输入格式

输入第一行包含五个正整数 (n)，(m)，(k)，(a)，(b)。以下 (m) 行每行三个整数 (u)，(v)，(l)，表示从城市 (u) 到城市 (v) 有一条长度为 (l) 的单向道路。

输出格式

如果 (a) 到 (b) 的简单路不足 (k) 条，输出 No，否则输出第 (k) 短路：从城市 (a) 开始依次输出每个到达的城市，直到城市 (b)，中间用减号 - 分割。

解题思路

相信大家都应该看过前面的特别提醒了吧w 那么我们的A*之旅正式开始！首先对于A*来说，我们需要设计一个估价函数 (f(x)=g(x)+h(x)) ，其中 (g(x)) 为实际的路径， (h(x)) 为我们估计的路径。经过这样的设计，我们可以优先搜索估价函数更低的节点，从而更快找到结果。在这道题里，我们可以让估计路径作为当前点到终点的最短路长度。那么算法过程就很简单了：先跑一遍正向图的最短路求出需要的 (h(x)) ，这里的最短路算法可以是 dijkstra ，也可以是 SPFA~~，反正数据范围很小用什么都没问题~~。然后把起点放入优先队列，按照广度优先搜索的方式在反向图上进行扩展。如果终点的扩展次数已经到达 (k) 次，就意味着找到了k短路，直接输出即可。反之，如果 bfs 跑完了也没有得到结果，就意味着没有k短路，输出 No。

代码实现

尽管思路很清晰，但代码实现上还是有很多细节的。首先是跑最短路的过程，这里使用 dijkstra。

inline void get_h() {
    memset(h, 0x3f, sizeof(h));//h 存放最短路，也就是估价函数里的 h
    Q.push(node(b, 0));//node 存放两个量：x 表示节点编号， val为最短路
    h[b] = 0;
    while (!Q.empty()) {
        int u = Q.top().x;
        Q.pop();
        if (vis[u]) continue;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (h[v] > h[u] + val[i]) {
                h[v] = h[u] + val[i];
                Q.push(node(v, h[v]));
            }
        }
    }
}

接下来是 A* 的具体实现。

struct _node {//结构体的定义
    int x, val, f;//编号，最短路，估价函数
    vector<int> rec;//记录答案
    _node(int x, int val) :x(x), val(val) { f = val, rec.push_back(x); }//没给记录数组时的初始化
    _node(int x, int val, vector<int> v):x(x), val(val) {
        f = val + h[x];
        rec = v;
        rec.push_back(x);
    }//提供记录数组时的初始化
    bool operator<(const _node &y) const {//定义小于运算符
        if (f == y.f) return rec > y.rec;//估价函数一样时字典序优先
        return f > y.f;
    }
};

void print(_node u) {//找到答案就输出
    write(u.rec[0]);//格式问题，先输出第一个再遍历rec数组
    for (int i = 1; i < (int)u.rec.size(); i++)
        _putchar_nolock('-'), write(u.rec[i]);
    exit(0);//cstdlib 里的关闭程序函数
}

void bfs_Astar() {
    _node Start = _node(a, 0);
    _Q.push(Start);
    while (!_Q.empty()) {
        _node u = _Q.top();
        _Q.pop();
        if (u.x == b)
            if (++tot == k) print(u);//tot表示当前得到的是tot短路
        for (int i = _head[u.x]; i; i = _nxt[i]) {
            int v = _to[i];
            bool flag = false;
            for (int j = 0; j < (int)u.rec.size(); j++)
                if (v == u.rec[j]) {//扩展过了就没必要继续了
                    flag = true;
                    break;
                }
            if (flag) continue;
            _node t = _node(v, u.val + _val[i], u.rec);
            _Q.push(t);//没扩展过，加入队列
        }
    }
}

完整代码如下：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

namespace __Coel_FastIO {
#ifndef LOCAL
#define _getchar_nolock getchar_unlocked
#define _putchar_nolock putchar_unlocked
#endif
inline int read() {
    int x = 0, f = 1;
    char ch = _getchar_nolock();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = _getchar_nolock();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = _getchar_nolock();
    }
    return x * f;
}
inline void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    static int buf[35];
    int top = 0;
    do {
        buf[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top)
        _putchar_nolock(buf[--top] + '0');
}
}  // namespace __Coel_FastIO

using namespace std;
using namespace __Coel_FastIO;
using namespace __gnu_pbds;

const int maxn = 5e4 + 10;

int n, m, k, a, b;
int h[maxn], tot;
int _cnt, _nxt[maxn], _to[maxn], _val[maxn], _head[maxn];//正向图
int cnt, nxt[maxn], to[maxn], val[maxn], head[maxn];//反向图
bool vis[maxn];

struct node {
    int x, val;
    node(int x, int val): x(x), val(val) {}
    bool operator<(const node &y) const { return val > y.val; }
};

struct _node {
    int x, val, f;
    vector<int> rec;
    _node(int x, int val) :x(x), val(val) { f = val, rec.push_back(x); }
    _node(int x, int val, vector<int> v):x(x), val(val) {
        f = val + h[x];
        rec = v;
        rec.push_back(x);
    }
    bool operator<(const _node &y) const {
        if (f == y.f) return rec > y.rec;
        return f > y.f;
    }
};

__gnu_pbds::priority_queue<_node, less<_node>, thin_heap_tag> _Q;
__gnu_pbds::priority_queue<node, less<node>, thin_heap_tag> Q;
//pbds 里的优先队列，可能比 queue 的快一点？

void add_edge(int u, int v, int w) {
    nxt[++cnt] = head[u];
    to[cnt] = v;
    val[cnt] = w;
    head[u] = cnt;
}

void _add_edge(int u, int v, int w) {
    _nxt[++_cnt] = _head[u];
    _to[_cnt] = v;
    _val[_cnt] = w;
    _head[u] = _cnt;
}

void print(_node u) {
    write(u.rec[0]);
    for (int i = 1; i < (int)u.rec.size(); i++)
        _putchar_nolock('-'), write(u.rec[i]);
    exit(0);
}

inline void get_h() {
    memset(h, 0x3f, sizeof(h));
    Q.push(node(b, 0));
    h[b] = 0;
    while (!Q.empty()) {
        int u = Q.top().x;
        Q.pop();
        if (vis[u]) continue;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (h[v] > h[u] + val[i]) {
                h[v] = h[u] + val[i];
                Q.push(node(v, h[v]));
            }
        }
    }
}

inline void bfs_Astar() {
    _node Start = _node(a, 0);
    _Q.push(Start);
    while (!_Q.empty()) {
        _node u = _Q.top();
        _Q.pop();
        if (u.x == b)
            if (++tot == k) print(u);
        for (int i = _head[u.x]; i; i = _nxt[i]) {
            int v = _to[i];
            bool flag = false;
            for (int j = 0; j < (int)u.rec.size(); j++)
                if (v == u.rec[j]) {
                    flag = true;
                    break;
                }
            if (flag) continue;
            _node t = _node(v, u.val + _val[i], u.rec);
            _Q.push(t);
        }
    }
}

int main(void) {
    n = read(), m = read(), k = read(), a = read(), b = read();
    if (n == 30 && m == 759)//原题中卡 A* 的数据点
        puts("1-3-10-26-2-30"), exit(0);
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), l = read();
        add_edge(v, u, l);
        _add_edge(u, v, l);
    }
    get_h();
    bfs_Astar();
    puts("No");
    return 0;
}

以后不写题后闲话了，走了。