第0010届初九杯G题题解

省流：

存在 $n$ 个点和 $m$ 条有向边，每个点含有点权，求 $st$ 点到
$ed$点的第 $k$ 短路。

解析：

在每一处地点所需要消耗的时间分为预计时间和实际时间，而实际时间是由当前点的预计时间和上一个点的预计时间取平均值（向下取整）而求得的，所以我们可以将这道题转化一下，由两点之间连接的边的边权来代替下一个点的点权，所以这道题就由求点权和变成了求边权和，此时就完完全全变成了一个标准的第 $k$ 短路题模板题。~~好的什么都会的群友们可以拿模板来拿双倍经验了~~

对于第 $k$ 短路， OI Wiki 上给出了两种解法 k短路-OI Wiki，一种是 $ A^* $ 算法，一种是可持久化可并堆优化 $k$ 短路算法，实际上对于大部分 $k$ 短路问题， $A^*$ 算法都不算是正解，~~但是我只会 $A^*$ 算法而且还非常半吊子~~ 所以就只能表述一下 $A^*$ 算法的实现。 ~~反正能过就行~~

A*算法

概述

A*搜索算法（$\text{A*search algorithm}$）是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历和最佳优先搜索算法，亦是 BFS 的优化，用到了启发式搜索的思维。
启发式搜索（$\text{heuristic search}$）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。
启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

过程

对于本题来说，确定了起点 $st$ 和终点 $ed$ ，对于每个点 $x$ ，计算出从 $st$ 开始的耗时函数 $g(x)$ ，到 $ed$ 的预估代价耗时函数 $h(x)$ 和$h^*(x)$ ，很显然能够得出启发式函数:

$f(x)=g(x)+h(x)$
$A^*$ 算法的正确性在保证对于任意一点 $x$，都有 $h \le h^*$。
类似 $ Dijikstra $ 算法，$A^*$ 算法每一次从优先队列中取出一个 $f$ 值最小的元素并以此更新相邻的所有状态。

不过，当 $h = 0$ 时，$A^*$ 算法退化为 $Dijkstra$ 算法，当 $h = 0$ 且边权为 $1$ 时，会演变为 $BFS$ 。对于 $A^*$ 算法来说，当图是一个 $n$ 元环时，算法的时间复杂度会退化为 $O(nk\ log\ n)$ 。~~所以某种意义意义上来说，本题数据比较水~~

题解思路

不难看出，这题可以用 $A^*$ 算法来解决，初始状态设为 $st$，终点为 $ed$，实际耗时函数 $g(x)$ 表示从 $st$ 到 $x$ 点的实际耗时，估价函数 $h(x)$ 表示从当前点到节点 $ed$ 的估计距离。

首先反向建图，对 $ed$ 点使用一次 $Dijkstra$ 算法预处理出 $st$ 点到达其他所有点的最短时间作为预估耗时函数 $g(x)$ ，然后将初始状态依次加入到队列当中，每次取出 $f$ 值最小的一项，计算出相邻的所有点并全部加入到队列当中。当第 $k$ 次走到节点 $ed$ 时，便是所得到的答案。

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define PII pair<int,int>

const int MAXN = 1e5 + 10;
const int INF = 0x3f;

int n, m, st, ed, k;
int dist[MAXN];
int cnt[MAXN];
int arr[MAXN];
bool vis[MAXN];

struct Edge
{
  int u, w;            // 出点，权值
  bool operator < (const Edge& u) const
  {
      return w > u.w;
  }
};                        // 存边用的结构体

vector<Edge> g[MAXN];        // 正向建图
vector<Edge> rg[MAXN];        // 反向建图

struct Node
{
  int f, g, idx;        // 估价值 + 真实值，真实值，编号
  bool operator<(const Node& u) const
  {
      return f > u.f;
  }
};

void dijkstra(void)            // 求出终点到起点时扩展过的所有点的路（被用来当作估价函数，因为其值不会小于实际距离）
{
  priority_queue<Edge> heap;
  memset(vis, 0, sizeof(vis));
  memset(dist, 0x3f, sizeof dist);
  heap.push({ ed, 0 });
  dist[ed] = 0;

  while (!heap.empty())
  {
      auto t = heap.top();    //懒得写特别长的类型名了所以直接auto（
      heap.pop();
      int u = t.u;
      if (vis[u])
          continue;

      vis[u] = true;

      for (auto y : rg[u])
      {
          int v = y.u, w = y.w;
          if (dist[v] > dist[u] + w)
          {
              dist[v] = dist[u] + w;
              heap.push({ v, dist[v] });
          }
      }
  }
}

int astar(void)
{
  priority_queue<Node> heap;
  heap.push({ dist[st], 0, st });    // 初始点到终点的f值为dist[st] + 0，起点到自身的距离为 0

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

      int idx = t.idx, distance = t.g;    // 取出编号和st点到该点的实际距离
      cnt[idx]++;                        // 小优化
      if (cnt[ed] == k)
          return distance;    // 如果终点遍历了 k 次，直接return掉
      for (auto y : g[idx])
      {
          int v = y.u, w = y.w;
          if (cnt[v] < k)
              heap.push({ distance + w + dist[v], distance + w, v });    // 该状态仍可扩展
      }
  }
  return -1;                        // 无解时直接return
}

signed main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
      cin >> arr[i];
  for (int i = 1; i <= m; i++)
  {
      int u, v;
      cin >> u >> v;
      int w = (arr[u] + arr[v]) / 2;
      g[u].push_back({ v, w });            // 正向建图
      rg[v].push_back({ u, w });        // 反向建图
  }

  cin >> st >> ed >> k;
  if (st == ed)
      k++;                    // 题目要求，至少要有一条路
  dijkstra();

  // cout << dist[st] << '\n';
  // if (dist[st] == INF) cout << -1 << '\n';
  int res = astar();
  if (res == -1)
      cout << "Saigyouji Yuyuko:o shi i." << endl;
  else
      cout << res << endl;

}

~~原谅我的半吊子A*和半吊子题解~~