如果可以的话，数据还需加强

https://www.zhihu.com/question/292283275/answer/2824896940 这个里面的 SPFA 代码可以过

#include <iostream>
#include <limits>
#include <map>
#include <utility>
namespace Solution {
constexpr bool is_UOJ = true, HAS_NEGATIVE_CYCLE = false;
constexpr std::size_t N = 300005u, M = 1000005u;
constexpr long long INF =
    is_UOJ ? std::numeric_limits<long long>::max() >> 7ll : 2147483647ll;
std::size_t n, m, head[N], cnt, in[N], step[N];
std::pair<long long, long long> status[N];
// status[i].first is the dis, while status[i].second is the diff.
std::multimap<long long, std::size_t>::iterator iter[N];
bool vis[N];
long long dis[N];
struct Edge {
  std::size_t to, nxt;
  long long dis;
} edge[M];
void AddEdge(const std::size_t &u, const std::size_t &v,
             const long long &w) noexcept {
  edge[++cnt] = (const Edge){v, head[u], w};
  head[u] = cnt;
}
void DFS(const std::size_t &curr) noexcept {
  vis[curr] = true;
  for (std::size_t i = head[curr]; i; i = edge[i].nxt)
    if (vis[edge[i].to] == false)
      DFS(edge[i].to);
}
bool SPFA(const std::size_t &s) noexcept {
  std::size_t reachable = 0u;
  if constexpr (HAS_NEGATIVE_CYCLE) {
    for (std::size_t i = 1u; i <= n; ++i)
      vis[i] = false;
    DFS(s);
    for (std::size_t i = 1u; i <= n; ++i)
      if (vis[i])
        ++reachable;
  } else
    reachable = n;
  std::multimap<long long, std::size_t> q;
  for (std::size_t i = 1u; i <= n; ++i) {
    status[i].first = dis[i] = INF;
    vis[i] = false;
    if constexpr (HAS_NEGATIVE_CYCLE)
      in[i] = step[i] = 0u;
    status[i].second = 0ll;
    iter[i] = q.end();
  }
  status[s].first = dis[s] = 0ll;
  vis[s] = true;
  if constexpr (HAS_NEGATIVE_CYCLE)
    in[s] = 1u;
  q.insert(std::make_pair(0ll, s));
  bool flag = false, is_modified = false;
  for (std::size_t u, i; !q.empty() && q.begin()->first <= 0ll;
       is_modified = flag = false) {
    u = q.begin()->second;
    if constexpr (HAS_NEGATIVE_CYCLE)
      if (step[u] >= reachable)
        return true;
    vis[u] = false;
    iter[u] = q.end();
    q.erase(q.begin());
    status[u].first = dis[u];
    for (i = head[u]; i; i = edge[i].nxt) {
      const long long &w = edge[i].dis;
      if (const std::size_t &v = edge[i].to; dis[v] > dis[u] + w) {
        if constexpr (HAS_NEGATIVE_CYCLE)
          if (v == s)
            return true;
        dis[v] = dis[u] + w;
        if constexpr (HAS_NEGATIVE_CYCLE)
          if (step[v] = step[u] + 1u; step[v] >= reachable)
            return true;
        if (!flag) {
          flag = true;
          status[u].second = 1ll;
        }
        if (head[v]) {
          if (!vis[v]) {
            if constexpr (HAS_NEGATIVE_CYCLE)
              if ((++in[v]) >= reachable)
                return true;
            vis[v] = true;
            iter[v] = q.insert(
                std::make_pair(status[v].second + dis[v] - status[v].first, v));
          } else {
            q.erase(iter[v]);
            iter[v] = q.insert(
                std::make_pair(status[v].second + dis[v] - status[v].first, v));
          }
        }
      } else if (!flag) {
        if (is_modified)
          status[u].second =
              std::min(status[u].second, dis[u] + w - dis[v] + 1ll);
        else {
          status[u].second = dis[u] + w - dis[v] + 1ll;
          is_modified = true;
        }
      }
    }
  }
  return false;
}
int main() noexcept {
  std::size_t s;
  std::cin >> n >> m >> s;
  long long w;
  for (std::size_t i = 0u, u, v; i != m; ++i) {
    std::cin >> u >> v >> w;
    AddEdge(u, v, w);
  }
  if (SPFA(s))
    std::cout << "NO";
  else
    for (std::size_t i = 1u; i <= n; ++i)
      std::cout << (is_UOJ ? (dis[i] == INF ? -1ll : dis[i]) : dis[i]) << ' ';
  return 0;
}
} // namespace Solution
int main() noexcept {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  return Solution::main();
}

另外如果管理在的话把我这题 AC 记录取消谢谢