WIKI

分层图最短路

分层图最短路，如：有 $k$ 次零代价通过一条路径，求总的最小花费。对于这种题目，我们可以采用 DP 相关的思想，设 $\text{dis}_{i, j}$ 表示当前从起点 $i$ 号结点，使用了 $j$ 次免费通行权限后的最短路径。显然，$\text{dis}$ 数组可以这么转移：

$\text{dis}_{i, j} = \min\{\min\{\text{dis}_{from, j - 1}\}, \min\{\text{dis}_{from,j} + w\}\}$

其中，$from$ 表示 $i$ 的父亲节点，$w$ 表示当前所走的边的边权。当 $j - 1 \geq k$ 时，$\text{dis}_{from, j}$=$\infty$。

事实上，这个 DP 就相当于把每个结点拆分成了 $k+1$ 个结点，每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说，就是每个结点 $u_i$ 表示使用 $i$ 次免费通行权限后到达 $u$ 结点。

例题

Slavic 的所有朋友都计划从他们居住的地方骑自行车去参加聚会。除了斯拉夫之外，他们都有自行车。他们可以穿越 $n$ 个城市。他们都住在城市 $1$ ，并且想去参加位于城市 $n$ 的聚会。城市地图可以看作是具有 $n$ 个节点和 $m$ 个边的无向图。边 $i$ 连接城市 $u_i$ 和 $v_i$ ，长度为 $w_i$ 。

斯拉夫没有自行车，但他有的是钱。每个城市都有一辆自行车待售。每辆自行车的慢度系数为 $s_{i}$ 。一旦 Slavic 购买了一辆自行车，他就可以随时使用它从当前所在城市前往任何邻近城市，只需花费 $w_i \cdot s_j$ 时间(考虑到他正在使用自己拥有的自行车 $j$ 穿越边缘 $i$ )。

斯拉夫可以购买任意数量的自行车，因为钱对他来说不是问题。由于 Slavic 讨厌骑自行车旅行，因此他希望在尽可能短的时间内从住处到达聚会场所。而且，由于他的信息学技能相当生疏，他向你寻求帮助。

斯拉夫语从城市 $1$ 到城市 $n$ 所需的最短时间是多少？斯拉夫人没有自行车就不能旅行。保证斯拉夫可以从城市 $1$ 前往任何其他城市。

输入

第一行包含一个整数 $t$ ( $1 \leq t \leq 100$ ) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个以空格分隔的整数 $n$ 和 $m$ ( $2 \leq n \leq 1000$ ; $n - 1 \leq m \leq 1000$ ) - 分别是城市数量和道路数量。

以下 $m$ 行中的第 $i$ 行每行包含三个整数 $u_i$ 、 $v_i$ 、 $w_i$ ( $1 \le u_i, v_i \le n$ 、 $u_i \neq v_i$ ； $1 \leq w_i \leq 10^5$ )，表示之间有一条路城市 $u_i$ 和 $v_i$ ，长度为 $w_i$ 。同一对城市可以通过多条道路连接。

下一行包含 $n$ 整数 $s_1, \ldots, s_n$ ( $1 \leq s_i \leq 1000$ ) - 每辆自行车的慢速系数。

所有测试用例的 $n$ 之和不超过 $1000$ ，所有测试用例的 $m$ 之和不超过 $1000$ 。

对输入的附加限制：可以从城市 $1$ 前往任何其他城市。

code

// Codeforces - Codeforces Round 918 (Div. 4) G. Bicycles
// https://codeforces.com/contest/1915/problem/G 2024-03-07 20:09:09

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
using pii = pair<int, int>;
using ijk = tuple<int, int, int>;
int chmin(int &x, int val) { return (x > val ? x = val : x); }
int n, m;
void solve() {
  cin >> n >> m;
  vector<int> w(n);
  priority_queue<ijk> q;
  vector<vector<pii>> G(n);
  vector<vector<int>> dp(n);
  for (int i = 0; i < m; i++) {
    int v, t, w;
    cin >> v >> t >> w;
    v--, t--;
    G[v].emplace_back(t, w);
    G[t].emplace_back(v, w);
  }
  for (auto &i : w) cin >> i;
  for (auto &i : dp) i.resize(n, LLONG_MAX);
  q.emplace(0, 0, 0);
  dp[0][0] = 0;
  while (q.size()) {
    auto [dist, idx, use] = q.top();
    q.pop();
    for (auto [to, val] : G[idx]) {
      int mn = (w[use] < w[to] ? use : to);
      if (val * w[use] - dist < dp[to][mn]) {
        dp[to][mn] = val * w[use] - dist;
        q.emplace(-dp[to][mn], to, mn);
      }
    }
  }
  int ans = LLONG_MAX;
  for (int i = 0; i < n; i++) chmin(ans, dp[n - 1][i]);
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int __;
  cin >> __;
  while (__--) solve();
  return 0;
}