本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-10 20:20:15

首先将删边改为加边，问题就转化为：向最初的无边图中依次加入 $M$ 到 $1$ 条边，求加入后的最短路。

我们设 $f(i)$ 代表从点 $1$ 走到点 $i$ 的最短路径，有边界：$f(1) = 0$。在加入每一条边 $(u,v)$ 的过程中，影响的只有 $v$：$f(v) = \min\{f(v), f(u) + w\}$。

更新完点 $v$ 之后，我们更新可能被点 $v$ 影响到的每一个点，即做一次 BFS。

作为出题人，有以下注意点：

• 本题不卡常，正确的算法应当都能通过，$O(m^2)$ 以上的暴力最短路不能通过。但是，STL 与手写可以差两倍时间。
• 本题的数据：Subtask 0 是生成数据，Subtask 1 是手写数据，包括样例

以下是标程：

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
#define rep(v, s, e) for (auto v = (s); v < (e); v++)
#define rrep(v, e, s) for (auto v = (e); v >= (s); v--)
using namespace std;

const long long N = 2 * 1000, M = 100000, K = 10, wtsummax = 1e10;
long long f[N], q[M], pt[K], wi[M], qs[M * K];
vector<pair<int, long long>> e[N];
int ui[M], vi[M];

int
read (void)
{
  int res = 0, sign = 1;
  char c;

  while (!isdigit (c = getchar ()))
    if (c == '-') sign = -1;
  do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
  return res * sign;
}

void
spread (int s)
{
  int head = 0, tail = 1;
  q[0] = s;

  while (head <= tail)
    {
      int p = q[head++];

      for (auto t : e[p])
        {
          int v = t.first, w = t.second;
          if (f[v] > f[p] + w)
            f[v] = f[p] + w, q[tail++] = v;
        }
    }
}

int
main (void)
{
  int m, k, tail = 0;

  read (), m = read (), k = read ();
  rep (i, 0, k) pt[i] = read () - 1;
  rep (i, 0, m) ui[i] = read () - 1, vi[i] = read () - 1, wi[i] = read ();

  memset (f, 0x3f, sizeof f);
  f[0] = 0;

  rrep (i, m - 1, 0)
    {
      int u = ui[i], v = vi[i]; long long w = wi[i];

      e[u].push_back (make_pair (v, w));
      if (f[v] > f[u] + w)
        {
          f[v] = f[u] + w;
          spread (v);
        }

      rrep (j, k - 1, 0) qs[tail++] = f[pt[j]] > wtsummax ? INT_MAX : f[pt[j]];
    }

  tail--;
  while (tail >= 0)
    {
      rep (i, 0, k) printf ("%lld ", qs[tail--]);
      putchar ('\n');
    }

  return 0;
}

关于复杂度：

这算法看起来是 $O(nm)$ 的，但卡不到，因为只有当前边更优的时候我们才会更新其他点，而且更新的点只是整个图很小的一部分。随机数据只到了大约二十到三十万的水平。